Представим следующий алгоритм. Есть массив \(v_1, v_2, \dots, v_n\), изначально заполненный нулями. Несколько раз с массивом проделываются похожие операции — на \(i\)-м шаге (в \(0\)-индексации) вы можете:
- либо выбрать любую позицию \(pos\) (\(1 \le pos \le n\)) и увеличить \(v_{pos}\) на \(k^i\);
- либо не выбирать позицию и пропустить шаг.
Вы можете выбирать, как алгоритм ведет себя на каждом шаге и когда он будет остановлен. Вопрос в следующем: можно ли сделать массив \(v\) равным некоторому массиву \(a\) (\(v_j = a_j\) для каждого \(j\)) после некоторого шага?
Выходные данные
Для каждого набора тестовых данных выведите либо YES (регистр не важен), если можно получить массив \(a\) после некоторого шага, либо NO (регистр не важен), если это невозможно.
Примечание
В первом наборе тестовых данных можно остановить алгоритм до \(0\)-го шага, или не выбирать никакую позицию и остановить алгоритм позже.
Во втором наборе можно прибавить \(k^0\) к \(v_1\) и остановить алгоритм.
В третьем наборе невозможно получить два элемента, равных \(1\), в массиве \(v\).
В пятом наборе можно пропустить \(9^0\) и \(9^1\), прибавить \(9^2\) и \(9^3\) к \(v_3\), пропустить \(9^4\) и, наконец, прибавить \(9^5\) к \(v_2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
4 100
0 0 0 0
1 2
1
3 4
1 4 1
3 2
0 1 3
3 9
0 59049 810
|
YES
YES
NO
NO
YES
|