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

Представим следующий алгоритм. Есть массив $$$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$$$) после некоторого шага?

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

В первой строке задано одно целое число $$$T$$$ ($$$1 \le T \le 1000$$$) — количество наборов входных данных. В следующих $$$2T$$$ строках заданы сами наборы входных данных, по две строки на каждый набор.

Первая строка каждого набора содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 30$$$, $$$2 \le k \le 100$$$) — размер массивов $$$v$$$ и $$$a$$$, и число $$$k$$$, используемое в алгоритме.

Во второй строке набора входных данных заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^{16}$$$) — массив, который вы хотите получить.

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

Для каждого набора тестовых данных выведите либо YES (регистр не важен), если можно получить массив $$$a$$$ после некоторого шага, либо NO (регистр не важен), если это невозможно.

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

В первом наборе тестовых данных можно остановить алгоритм до $$$0$$$-го шага, или не выбирать никакую позицию и остановить алгоритм позже.

Во втором наборе можно прибавить $$$k^0$$$ к $$$v_1$$$ и остановить алгоритм.

В третьем наборе невозможно получить два элемента, равных $$$1$$$, в массиве $$$v$$$.

В пятом наборе можно пропустить $$$9^0$$$ и $$$9^1$$$, прибавить $$$9^2$$$ и $$$9^3$$$ к $$$v_3$$$, пропустить $$$9^4$$$ и, наконец, прибавить $$$9^5$$$ к $$$v_2$$$.