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=[1]t=[1].

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].

SOLUTION

Click here

Leave a Comment

Your email address will not be published.