# Euclid Guess solution codeforces

## Euclid Guess solution codeforces

Let’s consider Euclid’s algorithm for finding the greatest common divisor, where tt 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 pp of pairs of positive integers that are not greater than mm. Initially, the list tt is empty. Then the function is run on each pair in pp. After that the list tt is shuffled and given to you.

You have to find an array pp of any size not greater than 21042⋅104 that produces the given list tt, or tell that no such array exists.

Input

## Euclid Guess solution codeforces

The first line contains two integers nn and mm (1n1031≤n≤1031m1091≤m≤109) — the length of the array tt and the constraint for integers in pairs.

The second line contains nn integers t1,t2,,tnt1,t2,…,tn (1tim1≤ti≤m) — the elements of the array tt.

Output
• If the answer does not exist, output 1−1.
• If the answer exists, in the first line output kk (1k21041≤k≤2⋅104) — the size of your array pp, i. e. the number of pairs in the answer.The ii-th of the next kk lines should contain two integers aiai and bibi (1ai,biA1≤ai,bi≤A) — the ii-th pair in pp.

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

Examples

## Euclid Guess solution codeforces

input

Copy
7 20
1 8 1 6 3 2 3

output

Copy
3
19 11
15 9
3 7

input

Copy
2 10
7 1

output

## Euclid Guess solution codeforces

Copy
-1
input

Copy
2 15
1 7

output

Copy
1
15 8

input

Copy
1 1000000000
845063470

output

## Euclid Guess solution codeforces

Copy
-1
Note

In the first sample let’s consider the array tt for each pair:

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

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

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

In the third test case for the pair (15,8)(15,8) array tt will be [7,1][7,1].