Яхуб играет в необычную игру. Изначально у него есть n коробок, пронумерованных 1, 2, 3, ..., n. В каждой коробке лежит некоторое количество конфет. В коробке с номером k лежит ak конфет.
Цель игры — переместить все конфеты ровно в 2 коробки. В оставшихся n - 2 коробках должно остаться ноль конфет. Для этого Яхуб должен сделать несколько (возможно, ноль) ходов. За один ход он выбирает две различные коробки i и j, такие, что ai ≤ aj. Затем, Яхуб перекладывает из коробки j в коробку i ровно ai конфет. Например, когда в двух коробках лежит одинаковое количество конфет, коробка номер j становится пустой.
Ваша задача — сказать Яхубу, какие ходы он должен сделать, чтобы достигнуть цели игры. Если Яхуб не может достигнуть цели для данной конфигурации коробок, выведите значение -1. Пожалуйста, обратите внимание, что если решение существует, вам не требуется искать решение с минимальным количеством ходов.
Выходные данные
Если решения не существует, выведите -1. В противном случае, в первой строке выведите целое число c (0 ≤ c ≤ 106) — количество ходов. В каждой из следующих c строк выведите два целых числа i и j (1 ≤ i, j ≤ n, i ≠ j): числа i и j в k-ой строке обозначают, что на k-ом ходу Вы перекладываете конфеты из коробки с номером j в коробку с номером i.
Примечание
В первом тестовом примере после первого хода коробки будут содержать 3, 12 и 3 конфет. После второго хода, коробки будут содержать 6, 12 и 0 конфет. Итак, все конфеты ровно в двух коробках, что и требуется.
Во втором тестовом примере, вы можете увидеть, что данная конфигурация изначально не подходит, так как все конфеты в одной коробке. Никакая операция не сможет этого изменить, поэтому решения не существует.
В третьем тестовом примере, все конфеты изначально в двух коробках. Таким образом, не требуется выполнять никаких ходов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3 6 9
|
2
2 3
1 3
|
|
2
|
3
0 1 0
|
-1
|
|
3
|
4
0 1 1 0
|
0
|