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