Виталий подарил Максиму на \(16\)-й день рождения \(n\) чисел \(1, 2, \ldots, n\). Максиму надоело играть в настольные игры на празднике, поэтому он решил поиграть с этими числами. За один ход Максим может выбрать два числа \(x\) и \(y\) среди тех, которые у него есть, выкинуть их и добавить вместо них два числа \(x + y\) и \(|x - y|\). Он хочет, чтобы после всех ходов все числа были равны, и сумма чисел была минимальна.
Помогите Максиму найти решение. Друзья Максима не хотят долго ждать, поэтому в решении должно быть не более \(20n\) ходов. Гарантируется, что при заданных ограничениях, если решение существует, то существует решение, которое делает все числа равными, минимизирует их сумму и при этом тратит не более \(20n\) ходов.
Выходные данные
Для каждого набора входных данных выведите \(-1\), если невозможно сделать все числа равными.
Иначе выведите одно число \(s\) (\(0 \le s \le 20n\)) — количество ходов. Далее выведите \(s\) строк. \(i\)-я строка должна содержать два числа \(x_i\) и \(y_i\) — числа, которые Максим должен выбрать на \(i\)-м ходу. После всех операций числа должны стать равными.
Не забудьте, что вам не только нужно сделать все числа равными, но и минимизировать их сумму. Гарантируется, что при заданных ограничениях, если решение существует, то существует решение, которое делает все числа равными, минимизирует их сумму и при этом тратит не более \(20n\) ходов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
2
3
|
-1
3
1 3
2 2
4 0
|