让我们考虑一下寻找最大公约数的欧几里得算法,其中 $$$t$$$ 是一个列表:
有一个数组 $$$p$$$,由不大于 $$$m$$$ 的正整数对组成。最初,列表 $$$t$$$ 是空的。然后该函数在 $$$p$$$ 中的每一对上运行。之后,列表 $$$t$$$ 会被打乱并提供给您。
你必须找到一个大小不大于 $$$2 \cdot 10^4$$$ 的数组 $$$p$$$ 来生成给定列表 $$$t$$$,或者告诉不存在这样的数组。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 10^3$$$, $$$1 \le m \le 10^9$$$) - 数组 $$$t$$$ 的长度和成对整数的约束。
第二行包含 $$$n$$$ 整数 $$$t_1, t_2, \ldots, t_n$$$ ($$$1 \le t_i \le m$$$) — 数组 $$$t$$$ 的元素。
输出
- 如果答案不存在,则输出$$$-1$$$。
- 如果答案存在,则在第一行输出 $$$k$$$ ($$$1 \le k \le 2 \cdot 10^4$$$) - 数组 $$$p$$$ 的大小,i。 e.答案中的对数。接下来的 $$$k$$$ 行中的第 $$$i$$$ 应包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i, b_i \le m$$$) — $$$p$$$ 中的第 $$$i$$$ 对。
如果有多个有效答案,您可以输出其中任何一个。
示例
输入 #1
7 20 1 8 1 6 3 2 3
输出 #1
3 19 11 15 9 3 7
输入 #2
2 10 7 1
输出 #2
-1
输入 #3
2 15 1 7
输出 #3
1 15 8
输入#4
1 1000000000 845063470
输出#4
-1
注意
在第一个示例中,我们考虑每对的数组 $$$t$$$:
- $$$(19,\, 11)$$$: $$$t = [8, 3, 2, 1]$$$;
- $$$(15,\, 9)$$$: $$$t = [6, 3]$$$;
- $$$(3,\, 7)$$$:$$$t = [1]$$$。
因此总共 $$$t = [8, 3, 2, 1, 6, 3, 1]$$$,与输入 $$$t$$$ 相同(最多排列)。
在第二个测试用例中,不可能找到所有整数不大于 $$$10$$$ 并且 $$$t = [7, 1]$$$ 的数组 $$$p$$$
在 $$$(15,\, 8)$$$ 数组的第三个测试用例中,$$$t$$$ 将为 $$$[7, 1]$$$。