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\) за несколько (возможно, ноль) операций.
Выходные данные
Для каждого набора входных данных выведите Yes, если существует способ преобразовать \(a\) в \(b\), и 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}]\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|
Yes
Yes
No
Yes
No
|