У Ashish есть массив \(a\), состоящий из \(2n\) положительных целых чисел. Он хочет сжать массив \(a\) в массив \(b\) размера \(n-1\). Чтобы это сделать, он сначала выбирает ровно \(2\) (любые два) элемента массива \(a\) и удаляет их из массива. После этого он выполняет следующую операцию, пока массив \(a\) не пустой:
- удалить любые два элемента из массива \(a\) и добавить их сумму в массив \(b\).
Получившийся массив \(b\) должен удовлетворять одному условию. Наибольший общий делитель (\(\mathrm{gcd}\)) всех элементов массива должен быть больше \(1\).
Напомним, что наибольший общий делитель (\(\mathrm{gcd}\)) массива положительных целых чисел равен наибольшему целому числу, которое является делителем всех элементов массива.
Можно доказать, что всегда можно таким образом сжать массив \(a\) в массив \(b\) размера \(n-1\), так что \(gcd(b_1, b_2..., b_{n-1}) > 1\).
Помогите Ashish найти способ это сделать.
Выходные данные
Для каждого набора входных данных, выведите \(n-1\) строку — выполненные операции, чтобы сжать массив \(a\) в массив \(b\). Изначальное удаление двух элементов не является операцией и про это действие не нужно ничего выводить.
В \(i\)-й из этих строк должно находиться два целых числа, индексы (нумерация с \(1\)) двух элементов массива \(a\), которые используются в \(i\)-й операции. Все \(2n-2\) выведенных индекса должны быть различными целыми числами от \(1\) до \(2n\).
Вам не нужно выводить индексы двух изначально удаленных элементов из массива \(a\).
Если есть несколько возможных ответов, вы можете найти любой.
Примечание
В первом наборе входных данных \(b = \{3+6, 4+5\} = \{9, 9\}\) и \(\mathrm{gcd}(9, 9) = 9\).
Во втором наборе входных данных \(b = \{9+10\} = \{19\}\) и \(\mathrm{gcd}(19) = 19\).
В третьем наборе входных данных \(b = \{1+2, 3+3, 4+5, 90+3\} = \{3, 6, 9, 93\}\) и \(\mathrm{gcd}(3, 6, 9, 93) = 3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3
1 2 3 4 5 6
2
5 7 9 10
5
1 3 3 4 5 90 100 101 2 3
|
3 6
4 5
3 4
1 9
2 3
4 5
6 10
|