[Solution] Fishingprince Plays With Array Codeforces Solution

[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 [a1,a2,…,an]$[a_1,a_2,\dots ,a_n]$. He also has a magic number m$m$.

He can do the following two operations on it:

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

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

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

Fishingprince has another array [b1,b2,…,bk]$[b_1,b_2,\dots ,b_k]$. Please determine if he can turn a$a$ into b$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$t$ (1≤t≤104$1\le t\le {10}^4$). Description of the test cases follows.

NIT orz! Codeforces Solution

NIT Destroys the Universe Codeforces Solution 

Fishingprince Plays With Array Codeforces Solution

Permutation Graph Codeforces Solution

Placing Jinas Codeforces Solution 

Tree Recovery Codeforces Solution

Fishingprince Plays With Array Again Codeforces Solution

Maximum Product? Codeforces Solution

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

The second line of each test case contains n$n$ integers a1,a2,…,an$a_1,a_2,\dots ,a_n$ (1≤ai≤109$1\le a_i\le {10}^9$).

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

The fourth line of each test case contains k$k$ integers b1,b2,…,bk$b_1,b_2,\dots ,b_k$ (1≤bi≤109$1\le b_i\le {10}^9$).

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

Output

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