CF1696C.Fishingprince Plays With Array

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

Fishingprince is playing with an array $[a_1,a_2,\dots,a_n]$ . 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=[2,3]$ and $i=1$ , $a$ changes into $[1,1,3]$ .
Select $1\le i\le n-m+1$ such that $a_i=a_{i+1}=\dots=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=[3,2,2,3]$ and $i=2$ , $a$ changes into $[3,4,3]$ .

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 $[b_1,b_2,\dots,b_k]$ . Please determine if he can turn $a$ into $b$ using any number (possibly zero) of operations.

输入格式

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,\ldots,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,\ldots,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$ .

输出格式

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).

输入输出样例

输入#1

5
5 2
1 2 2 4 2
4
1 4 4 2
6 2
1 2 2 8 2 2
2
1 16
8 3
3 3 3 3 3 3 3 3
4
6 6 6 6
8 3
3 9 6 3 12 12 36 12
16
9 3 2 2 2 3 4 12 4 12 4 12 4 12 4 4
8 3
3 9 6 3 12 12 36 12
7
12 2 4 3 4 12 56

输出#1

Yes
Yes
No
Yes
No

说明/提示

In the first test case of the sample, we can do the second operation with $i=2$ : $[1,\color{red}{2,2},4,2]\to [1,\color{red}{4},4,2]$ .

In the second testcase of the sample, we can:

do the second operation with $i=2$ : $[1,\color{red}{2,2},8,2,2]\to [1,\color{red}{4},8,2,2]$ .
do the second operation with $i=4$ : $[1,4,8,\color{red}{2,2}]\to [1,4,8,\color{red}{4}]$ .
do the first operation with $i=3$ : $[1,4,\color{red}{8},4]\to [1,4,\color{red}{4,4},4]$ .
do the second operation with $i=2$ : $[1,\color{red}{4,4},4,4]\to [1,\color{red}{8},4,4]$ .
do the second operation with $i=3$ : $[1,8,\color{red}{4,4}]\to [1,8,\color{red}{8}]$ .
do the second operation with $i=2$ : $[1,\color{red}{8,8}]\to [1,\color{red}{16}]$ .

首页