Вам дан массив \(a\), состоящий из \(n\) целых положительных чисел. Вы можете совершать над ним операцию, состоящую из следующей последовательности действий:
- выбрать пару элементов \(a_i\) и \(a_j\) (\(1 \le i, j \le n\) и \(i \neq j\));
- выбрать один из делителей числа \(a_i\), то есть число \(x\) такое, что \(a_i \bmod x = 0\);
- заменить \(a_i\) на \(\frac{a_i}{x}\) и \(a_j\) на \(a_j \cdot x\).
Определите, можно ли, применив операцию к массиву некоторое количество раз (возможно, нулевое) сделать все элементы в массиве одинаковыми?
Например, пусть дан массив \(a\) = [\(100, 2, 50, 10, 1\)], состоящий из \(5\) элементов. Произведем над ним две операции:
- Выберем \(a_3 = 50\) и \(a_2 = 2\), \(x = 5\). Заменим \(a_3\) на \(\frac{a_3}{x} = \frac{50}{5} = 10\), \(a_2\) на \(a_2 \cdot x = 2 \cdot 5 = 10\). Получим массив \(a\) = [\(100, 10, 10, 10, 1\)];
- Выберем \(a_1 = 100\) и \(a_5 = 1\), \(x = 10\). Заменим \(a_1\) на \(\frac{a_1}{x} = \frac{100}{10} = 10\), \(a_5\) на \(a_5 \cdot x = 1 \cdot 10 = 10\). Получим массив \(a\) = [\(10, 10, 10, 10, 10\)].
После выполнения данных операций все элементы массива
\(a\) стали равны
\(10\).
Выходные данные
Для каждого набора входных данных в отдельной строке выведите:
- «YES», если можно сделать элементы массива равными, применяя операцию некоторое (возможно, нулевое) количество раз;
- «NO» в противном случае.
Вы можете выводить ответ в любом регистре (например, строки «yEs», «yes», «Yes» и «YES» будут распознаны как положительный ответ).
Примечание
Первый набор входных данных разобран в условии задачи.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
5
100 2 50 10 1
3
1 1 1
4
8 2 4 2
4
30 50 27 20
2
75 40
2
4 4
3
2 3 1
|
YES
YES
NO
YES
NO
YES
NO
|