C. Fishingprince играет с массивом
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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$$$ на $$$m$$$ копий числа $$$\frac{a_i}{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$$$.

Выходные данные

Для каждого набора входных данных выведите Yes, если существует способ преобразовать $$$a$$$ в $$$b$$$, и No иначе. Вы можете выводить каждый символ в любом регистре (верхнем или нижнем).

Пример
Входные данные
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
Выходные данные
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}]$$$.