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

На доске написано $$$n$$$ положительных чисел. Также выбрано положительное число $$$k \geq 2$$$, и ни одно из написанных чисел не делится на $$$k$$$. За одну операцию разрешается стереть с доски любые два числа $$$x$$$ и $$$y$$$ и записать вместо них $$$f(x + y)$$$, где $$$f(x)$$$ равно $$$x$$$, если $$$x$$$ не делится на $$$k$$$, и $$$f(x) = f(x / k)$$$ в противном случае.

В конце на доске останется одно число. Возможно ли сделать это число равным $$$1$$$? Если это так, восстановите любую последовательность операций, которая к этому приводит.

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

В первой строке записано два целых числа $$$n$$$ и $$$k$$$ — исходное количество чисел на доске и выбранное число ($$$2 \leq n \leq 16$$$, $$$2 \leq k \leq 2000$$$).

Во второй строке записано $$$n$$$ положительных чисел $$$a_1, \ldots, a_n$$$, изначально написанных на доске. Гарантируется, что ни одно из чисел $$$a_i$$$ не делится на $$$k$$$, а также сумма всех $$$a_i$$$ не превосходит $$$2000$$$.

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

Если получить $$$1$$$ в качестве последнего числа невозможно, выведите единственную строку «NO».

В противном случае, в первой строке выведите «YES», а затем выведите $$$n - 1$$$ строку с описанием операций. $$$i$$$-я из этих строк должна содержать два целых числа $$$x_i$$$ и $$$y_i$$$, которые необходимо заменить на $$$f(x_i + y_i)$$$ на $$$i$$$-й операции. Если существует несколько подходящих последовательностей, выведите любую из них.

Примеры
Входные данные
2 2
1 1
Выходные данные
YES
1 1
Входные данные
4 3
7 8 13 23
Выходные данные
YES
23 13
8 7
5 4
Входные данные
3 4
1 2 3
Выходные данные
NO
Примечание

Во втором примере:

  • $$$f(8 + 7) = f(15) = f(5) = 5$$$;
  • $$$f(23 + 13) = f(36) = f(12) = f(4) = 4$$$;
  • $$$f(5 + 4) = f(9) = f(3) = f(1) = 1$$$.