G. Алгоритм Люсине
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Принято считать, что самый известный алгоритм нахождения наибольшего общего делителя двух чисел придумал Евклид, однако на самом деле этот алгоритм придумала именно Тётя Люсине. Вы, должно быть, уже не удивились, ведь она — величайший ум человечества. И теперь она решила модернизировать этот алгоритм, привнеся в него немного креатива. А в вас есть эта жилка креатива?

Рассмотрим алгоритм Люсине для нахождения наибольшего общего делителя, где $$$t$$$ это некоторый список:


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

    if b == 0:
        return a

    r = остаток от деления a на b
    if r > 0:
        добавить r в конец t

    return Euclid(b, r)

Существует массив $$$p$$$ пар положительных целых чисел, каждое из них не больше $$$m$$$. Изначально список $$$t$$$ пустой. Описанная выше функция запускается на каждой паре из массива $$$p$$$. После этого вам даётся перестановка элементов $$$t$$$.

Вам необходимо найти массив $$$p$$$ любого размера не больше $$$2 \cdot 10^4$$$ такой, что по описанному алгоритму из него получится массив $$$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$$$.

Выходные данные
  • Если ответа не существует, выведите $$$-1$$$.
  • Если ответ существует, в первой строке выведите $$$k$$$ ($$$1 \le k \le 2 \cdot 10^4$$$) — размер массива $$$p$$$, т. е. количество пар в вашем ответе. $$$i$$$-я из следующих $$$k$$$ строк должна содержать два целых числа $$$a_i$$$ и $$$b_i$$$ ($$$1 \le a_i, b_i \le m$$$) — $$$i$$$-я пара массива $$$p$$$.

Если существуют несколько решений, вы можете вывести любой из них.

Примеры
Входные данные
7 20
1 8 1 6 3 2 3
Выходные данные
3
19 11
15 9
3 7
Входные данные
2 10
7 1
Выходные данные
-1
Входные данные
2 15
1 7
Выходные данные
1
15 8
Входные данные
1 1000000000
845063470
Выходные данные
-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]$$$.