На доске написано \(n\) положительных чисел. Также выбрано положительное число \(k \geq 2\), и ни одно из написанных чисел не делится на \(k\). За одну операцию разрешается стереть с доски любые два числа \(x\) и \(y\) и записать вместо них \(f(x + y)\), где \(f(x)\) равно \(x\), если \(x\) не делится на \(k\), и \(f(x) = f(x / k)\) в противном случае.
В конце на доске останется одно число. Возможно ли сделать это число равным \(1\)? Если это так, восстановите любую последовательность операций, которая к этому приводит.
Выходные данные
Если получить \(1\) в качестве последнего числа невозможно, выведите единственную строку «NO».
В противном случае, в первой строке выведите «YES», а затем выведите \(n - 1\) строку с описанием операций. \(i\)-я из этих строк должна содержать два целых числа \(x_i\) и \(y_i\), которые необходимо заменить на \(f(x_i + y_i)\) на \(i\)-й операции. Если существует несколько подходящих последовательностей, выведите любую из них.
Примечание
Во втором примере:
- \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 2
1 1
|
YES
1 1
|
|
2
|
4 3
7 8 13 23
|
YES
23 13
8 7
5 4
|
|
3
|
3 4
1 2 3
|
NO
|