← 返回题目列表

Codeforces · 1225/G

G. 制作 1

中文机器翻译题面 查看原题

黑板上写着$$$n$$$个正整数。另外,选择正数 $$$k \geq 2$$$,并且黑板上的数字都不能被 $$$k$$$ 整除。在一次运算中,您可以选择任意两个整数 $$$x$$$ 和 $$$y$$$,将其擦除并写入一个额外的数字 $$$f(x + y)$$$,其中,如果 $$$x$$$ 不能被 $$$k$$$ 整除,则 $$$f(x)$$$ 等于 $$$x$$$,否则 $$$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$$$,以便在第 $$$i$$$ 操作中擦除并替换为 $$$f(x_i + y_i)$$$。如果有多种合适的方式,则输出其中任何一种。

示例

输入 #1

2 2
1 1

输出 #1

YES
1 1

输入 #2

4 3
7 8 13 23

输出 #2

YES
23 13
8 7
5 4

输入 #3

3 4
1 2 3

输出 #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$$$。