## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## Euclid Guess Codeforces Solution | Codeforces Problem Solution 2022

G. Euclid Guess
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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},\dots ,{t}_{n}$ ($1\le {t}_{i}\le m$) — the elements of the array $t$.

Output
• 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 A$) — the $i$-th pair in $p$.

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