← 返回题目列表

Codeforces · 1696/C

C. Fishingprince 玩数组

中文机器翻译题面 查看原题

Fishingprince 正在玩数组 $$$[a_1,a_2,\dots,a_n]$$$。他还有一个神奇的数字$$$m$$$。

他可以对其进行以下两个操作:

- 选择 $$$1\le i\le n$$$ 使得 $$$a_i$$$ 可以被 $$$m$$$ 整除(也就是说,存在一个整数 $$$t$$$ 使得 $$$m \cdot t = a_i$$$)。将 $$$a_i$$$ 替换为 $$$\frac{a_i}{m}$$$ 的 $$$m$$$ 副本。其他元素的顺序不会改变。例如,当 $$$m=2$$$ 且 $$$a=[2,3]$$$ 且 $$$i=1$$$ 时,$$$a$$$ 变为 $$$[1,1,3]$$$。
- 选择$$$1\le i\le n-m+1$$$,使得$$$a_i=a_{i+1}=\dots=a_{i+m-1}$$$。将这些 $$$m$$$ 元素替换为单个 $$$m \cdot a_i$$$。其他元素的顺序不会改变。例如,当 $$$m=2$$$ 且 $$$a=[3,2,2,3]$$$ 且 $$$i=2$$$ 时,$$$a$$$ 变为 $$$[3,4,3]$$$。

请注意,在此过程中数组长度可能会发生变化。上面 $$$n$$$ 的值定义为数组的当前长度(可能与输入中的 $$$n$$$ 不同)。

Fishingprince 还有另一个数组 $$$[b_1,b_2,\dots,b_k]$$$。请确定他是否可以使用任意次数(可能为零)的运算将 $$$a$$$ 转换为 $$$b$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1\le n\le 5\cdot 10^4$$$, $$$2\le m\le 10^9$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le 10^9$$$)。

每个测试用例的第三行包含一个整数 $$$k$$$ ($$$1\le k\le 5\cdot 10^4$$$)。

每个测试用例的第四行包含 $$$k$$$ 整数 $$$b_1,b_2,\ldots,b_k$$$ ($$$1\le b_i\le 10^9$$$)。

保证所有测试用例的 $$$n+k$$$ 总和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,如果可以将 $$$a$$$ 转换为 $$$b$$$,则打印 Yes,否则打印 No。您可以以任何大小写(大写或小写)打印每个字母。

示例

输入 #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

注意

在样本的第一个测试用例中,我们可以用 $$$i=2$$$ 进行第二个操作:$$$[1,\color{red}{2,2},4,2]\to [1,\color{red}{4},4,2]$$$。

在示例的第二个测试用例中,我们可以:

- 使用 $$$i=2$$$ 执行第二个操作:$$$[1,\color{red}{2,2},8,2,2]\to [1,\color{red}{4},8,2,2]$$$。
- 使用 $$$i=4$$$ 执行第二个操作:$$$[1,4,8,\color{red}{2,2}]\to [1,4,8,\color{red}{4}]$$$。
- 使用 $$$i=3$$$ 执行第一个操作:$$$[1,4,\color{red}{8},4]\to [1,4,\color{red}{4,4},4]$$$。
- 使用 $$$i=2$$$ 执行第二个操作:$$$[1,\color{red}{4,4},4,4]\to [1,\color{red}{8},4,4]$$$。
- 使用 $$$i=3$$$ 执行第二个操作:$$$[1,8,\color{red}{4,4}]\to [1,8,\color{red}{8}]$$$。
- 使用 $$$i=2$$$ 执行第二个操作:$$$[1,\color{red}{8,8}]\to [1,\color{red}{16}]$$$。