## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## [Solution] Fishingprince Plays With Array Codeforces Solution

C. Fishingprince Plays With Array
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Fishingprince is playing with an array $\left[{a}_{1},{a}_{2},\dots ,{a}_{n}\right]$. He also has a magic number $m$.

He can do the following two operations on it:

• Select $1\le i\le n$ such that ${a}_{i}$ is divisible by $m$ (that is, there exists an integer $t$ such that $m\cdot t={a}_{i}$). Replace ${a}_{i}$ with $m$ copies of $\frac{{a}_{i}}{m}$. The order of the other elements doesn't change. For example, when $m=2$ and $a=\left[2,3\right]$ and $i=1$$a$ changes into $\left[1,1,3\right]$.
• Select $1\le i\le n-m+1$ such that ${a}_{i}={a}_{i+1}=\cdots ={a}_{i+m-1}$. Replace these $m$ elements with a single $m\cdot {a}_{i}$. The order of the other elements doesn't change. For example, when $m=2$ and $a=\left[3,2,2,3\right]$ and $i=2$$a$ changes into $\left[3,4,3\right]$.

Solution Click Below:-  👉
👇👇👇👇👇

Note that the array length might change during the process. The value of $n$ above is defined as the current length of the array (might differ from the $n$ in the input).

Fishingprince has another array $\left[{b}_{1},{b}_{2},\dots ,{b}_{k}\right]$. Please determine if he can turn $a$ into $b$ using any number (possibly zero) of operations.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le {10}^{4}$). Description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($1\le n\le 5\cdot {10}^{4}$$2\le m\le {10}^{9}$).

The second line of each test case contains $n$ integers ${a}_{1},{a}_{2},\dots ,{a}_{n}$ ($1\le {a}_{i}\le {10}^{9}$).

The third line of each test case contains one integer $k$ ($1\le k\le 5\cdot {10}^{4}$).

The fourth line of each test case contains $k$ integers ${b}_{1},{b}_{2},\dots ,{b}_{k}$ ($1\le {b}_{i}\le {10}^{9}$).

It is guaranteed that the sum of $n+k$ over all test cases does not exceed $2\cdot {10}^{5}$.

Output

For each testcase, print Yes if it is possible to turn $a$ into $b$, and No otherwise. You can print each letter in any case (upper or lower).