Пенчик любит две вещи: полные квадраты и булочки барбекю в гонконгском стиле! На его день рождения Коханэ хочет объединить их в один подарок: \(n\) булочек барбекю, расположенных слева направо. Существует \(10^6\) доступных начинок для булочек барбекю, пронумерованных от \(1\) до \(10^6\). Чтобы убедиться, что Пенчику понравится этот подарок, Кохане хочет, чтобы выполнялись следующие условия:
- Ни одна начинка не используется ровно один раз; то есть каждая начинка должна либо не появляться вовсе, либо появляться как минимум дважды.
- Для любых двух булочек \(i\) и \(j\) с одинаковой начинкой расстояние между ними, равное \(|i-j|\), должно быть полным квадратом\(^{\text{∗}}\).
Помогите Кохане найти подходящий способ выбора начинки для булочек или определите, что выполнить все условия невозможно. Если существует несколько решений, выведите любое из них.
Выходные данные
Для каждого набора входных данных, если не существует правильного выбора начинок, выведите \(-1\). В противном случае выведите \(n\) целых чисел, где \(i\)-е целое число представляет начинку \(i\)-й булочки барбекю. Если существует несколько решений, выведите любое из них.
Примечание
В первом наборе входных данных выбор начинок «1 1 1» недопустим, так как булочки \(1\) и \(3\) имеют одинаковую начинку, но находятся на расстоянии \(2\) друг от друга, что не является полным квадратом. Выбор начинок «1 1 2» также недопустим, так как начинка \(2\) используется только один раз.
Во втором наборе входных данных решение корректно, так как ни одна начинка не используется ровно один раз, и любые две булочки с одной и той же начинкой находятся на расстоянии, равном полному квадрату. Например, булочки \(1\) и \(10\) имеют начинку \(1\) и находятся на расстоянии \(9=3^2\). Аналогично, булочки \(5\) и \(9\) имеют начинку \(10\) и находятся на расстоянии \(4=2^2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
3
12
|
-1
1 2 3 6 10 2 7 6 10 1 7 3
|