Наибольший общий делитель (НОД) — это фундаментальное понятие в математике, которое помогает нам понять взаимосвязь между двумя числами. Это наибольшее положительное целое число, которое делит два разных числа без остатка.

Нахождение НОД — важный навык, который можно использовать во многих областях математики, включая алгебру, теорию чисел и криптографию. Например, в криптографии безопасность некоторых схем шифрования зависит от сложности нахождения НОД двух больших простых чисел.

Однажды Алекс решил бросить вызов самому себе, придумав собственный алгоритм шифрования с использованием НОД. Он изучал различные методы шифрования и был вдохновлен на создание чего-то нового и уникального.

Алекс часами изучал учебники и искал информацию в Интернете, пытаясь найти способ создать надежный и простой в использовании алгоритм шифрования.

Вместо больших простых чисел он решил кодировать свои данные одним массивом положительных целых чисел $$$a_1, \ldots, a_n$$$. Этот массив имеет значение только если он упорядочен в определенном порядке, поэтому Алекс хорошим образом перемешал свой массив.

Алекс знает, что изначальный порядок имел очень особенное свойство: числа $$$(a_i + i)$$$ не были взаимно простыми. Более формально, выполнялось условие $$$\text{НОД}(a_1 + 1, a_2 + 2, \ldots, a_n + n) \neq 1$$$.

Вскоре Алекс заметил, что расшифровать его шифр — далеко не одна из простых задач. У него есть уже перемешанный массив $$$a_1, \ldots, a_n$$$ длины $$$n$$$. Помогите ему восстановить изначальный порядок массива или сообщите Алексу что такого порядка не существует и он где-то ошибся. Если таких порядков может быть несколько, можно вывести любой.