Euclid Guess
Contest: Codeforces Round 792 (Div. 1 + Div. 2)
Difficulty rating: 2800
Tags: constructive algorithms, flows, graph matchings, math, number theory

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

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.

Input format:
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$$$.

Output format:
- 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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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]$$$.

Example input:
7 20
1 8 1 6 3 2 3

Example output:
3
19 11
15 9
3 7

Example input:
2 10
7 1

Example output:
-1

Editorial:
Let's consider some pair $$$(a, b)$$$ and consider a sequence of remainders that is induced by this pair: $$$a \bmod b = x_1$$$, $$$b \bmod x_1 = x_2$$$, ..., $$$x_{p - 2} \bmod x_{p - 1} = x_p$$$, where $$$x_p = gcd(a, b)$$$.
If $$$x_i \le \frac{m}{3}$$$ then we can just add a pair $$$(3x_i, 2x_i)$$$ and we will get the only remainder $$$x_i$$$ so these values will not be a problem.
If $$$x_1 > \frac{m}{3}$$$ (if $$$i > 1$$$ then $$$x_i \le \frac{m}{3}$$$) then $$$a = b + x_1$$$ because if $$$a \ge 2b + x_1$$$ then $$$a > m$$$ which is impossible. $$$b = x_1 + x_2$$$ because if $$$b \ge 2x_1 + x_2$$$ then $$$a \ge 3x_1 + x_2 > m$$$. Then $$$a = b + x_1 = 2x_1 + x_2 \ge 2x_1 + x_p$$$ because $$$x_p < x_{p - 1} < \ldots < x_2 < x_1$$$.
It means that for each $$$x_i > \frac{m}{3}$$$ there should be such $$$x_j$$$ that $$$2x_i + x_j \le m$$$ and $$$x_j$$$ is a divisor of $$$x_i$$$. For such values we can consider a bipartite graph where in the left part there are only $$$x_i > \frac{m}{3}$$$ and in the right part there are only $$$x_j \le \frac{m}{3}$$$ and two integers are connected $$$\iff$$$ the integer on the right divies the left one. This graph can be built in $$$O(n^2)$$$. After that we just have to find such matching that covers each integer in the left part and add all unused integers from the right part using the method above.