CF1684G.Euclid Guess

Let's consider Euclid's algorithm for finding the greatest common divisor, where $t$ is a list:

function Euclid(a, b):
if a < b:
swap(a, b)

if b == 0:
return a

r = reminder from dividing a by b
if r > 0:
append r to the back of t

return Euclid(b, r)

There is an array $p$ of pairs of positive integers that are not greater than $m$. Initially, the list $t$ is empty. Then the function is run on each pair in $p$. After that the list $t$ is shuffled and given to you.

You have to find an array $p$ of any size not greater than $2 \cdot 10^4$ that produces the given list $t$, or tell that no such array exists.

我们来考虑用于求最大公约数的欧几里得算法，其中 $t$ 是一个列表：

函数 Euclid(a, b):
若 a < b:
交换 a 和 b

若 b == 0:
返回 a

r = a 除以 b 的余数
若 r > 0:
将 r 追加到列表 t 的末尾

返回 Euclid(b, r)

给定一个由若干正整数对构成的数组 $p$，每对中的两个数均不超过 $m$。初始时列表 $t$ 为空。随后，对 $p$ 中的每一对数依次调用上述函数 Euclid。调用全部结束后，列表 $t$ 被随机打乱并交予你。

你需要构造一个长度不超过 $2 \cdot 10^4$ 的数组 $p$（其中每个元素为一对正整数），使得按上述过程运行后恰好生成（打乱前的）给定列表 $t$；若不存在这样的数组 $p$，则需指出无解。

The first line contains two integers $n$ and $m$ ($1 \le n \le 10^3$, $1 \le m \le 10^9$) — the length of the array $t$ and the constraint for integers in pairs.

The second line contains $n$ integers $t_1, t_2, \ldots, t_n$ ($1 \le t_i \le m$) — the elements of the array $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$ 的元素。

• If the answer does not exist, output $-1$.

• If the answer exists, in the first line output $k$ ($1 \le k \le 2 \cdot 10^4$) — the size of your array $p$, i. e. the number of pairs in the answer.

  The $i$-th of the next $k$ lines should contain two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le m$) — the $i$-th pair in $p$.

If there are multiple valid answers you can output any of them.

• 如果答案不存在，输出 $-1$。

• 如果答案存在，在第一行输出 $k$（$1 \le k \le 2 \cdot 10^4$）—— 即你构造的数组 $p$ 的大小，也就是答案中数对的个数。

  接下来的 $k$ 行中，第 $i$ 行应包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le m$）—— 即 $p$ 中的第 $i$ 个数对。

若存在多个合法答案，输出任意一个即可。

In the first sample let's consider the array $t$ for each pair:

• $(19,\, 11)$: $t = [8, 3, 2, 1]$;
• $(15,\, 9)$: $t = [6, 3]$;
• $(3,\, 7)$: $t = [1]$.

So in total $t = [8, 3, 2, 1, 6, 3, 1]$, which is the same as the input $t$ (up to a permutation).

In the second test case it is impossible to find such array $p$ of pairs that all integers are not greater than $10$ and $t = [7, 1]$

In the third test case for the pair $(15,\, 8)$ array $t$ will be $[7, 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$ 相同（允许元素顺序不同）。

在第二个测试用例中，无法找到满足条件的数对数组 $p$，使得所有整数均不超过 $10$，且 $t = [7, 1]$。

在第三个测试用例中，对于数对 $(15,\, 8)$，数组 $t$ 将为 $[7, 1]$。