Fishingprince Plays With Array

题意翻译

给定一个长度为 $n$ 的数组 $a$ 、一个长度为 $k$ 的数组 $b$ 和一个数字 $m$，现在对数组 $a$ 进行以下操作： - 选择数组 $a$ 中一个 $m$ 的倍数 $a_i$ 替换成 $m$ 个 $\dfrac{a_i}{m}$ - 选择数组 $a$ 中 $m$ 个相同的数字 $a_i,a_{i+1},\dots,a_{i+m-1}$ 替换成 $m\cdot a_i$ 请问能否把数组 $a$ 变成数组 $b$。 数据范围：$1\le n,k\le 5\times 10^4$，$2\le m\le 10^9$，$1\le a_i,b_i\le 10^9$，$\sum n+k\le 2\times 10^5$。

题目描述

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}] $ .

**题目大意：**
Fishingprince 正在玩一个数组 $[a_1,a_2,\dots,a_n]$，他有一个魔法数字 $m$。他可以在数组上进行以下两种操作：

1. 选择 $1 \le i \le n$ 使得 $a_i$ 能被 $m$ 整除，将 $a_i$ 替换成 $m$ 个 $\frac{a_i}{m}$。其他元素的顺序不变。例如，当 $m=2$ 且 $a=[2,3]$ 且 $i=1$ 时，$a$ 变成 $[1,1,3]$。
2. 选择 $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 \times 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 \times 10^4$）。
- 每个测试案例的第四行包含 $k$ 个整数 $b_1,b_2,\ldots,b_k$（$1 \le b_i \le 10^9$）。
- 保证所有测试案例的 $n+k$ 之和不超过 $2 \times 10^5$。

- **输出格式：**
- 对于每个测试案例，如果能将 $a$ 变成 $b$，则打印 "Yes"，否则打印 "No"。每个字母可以是大写或小写。**题目大意：** Fishingprince 正在玩一个数组 $[a_1,a_2,\dots,a_n]$，他有一个魔法数字 $m$。他可以在数组上进行以下两种操作： 1. 选择 $1 \le i \le n$ 使得 $a_i$ 能被 $m$ 整除，将 $a_i$ 替换成 $m$ 个 $\frac{a_i}{m}$。其他元素的顺序不变。例如，当 $m=2$ 且 $a=[2,3]$ 且 $i=1$ 时，$a$ 变成 $[1,1,3]$。 2. 选择 $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 \times 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 \times 10^4$）。 - 每个测试案例的第四行包含 $k$ 个整数 $b_1,b_2,\ldots,b_k$（$1 \le b_i \le 10^9$）。 - 保证所有测试案例的 $n+k$ 之和不超过 $2 \times 10^5$。 - **输出格式：** - 对于每个测试案例，如果能将 $a$ 变成 $b$，则打印 "Yes"，否则打印 "No"。每个字母可以是大写或小写。