| Codeforces Round 1013 (Div. 3) |
|---|
| Закончено |
В ИТ-кампусе «НЕЙМАРК» есть несколько совершенно секретных помещений, в которых ведется разработка задач к значимым олимпиадам по программированию. Чтобы попасть в такое помещение, нужно открыть круглый замок, подобрав верный код. Каждый день этот код обновляется.
Сегодня кодом является перестановка$$$^{\text{∗}}$$$ из чисел от $$$1$$$ до $$$n$$$, в каждом циклическом сдвиге$$$^{\text{†}}$$$ которой есть ровно одна неподвижная точка. То есть в каждом сдвиге существует число, значение которого совпадает с позицией в перестановке. Для лучшего понимания смотрите примечание к тестовым примерам.
Выведите любую подходящую перестановку. Имейте в виду, что подходящей перестановки может не существовать, а значит, сегодня помещение не работает, в таком случае выведите $$$-1$$$.
$$$^{\text{∗}}$$$Перестановкой будем называть последовательность длины $$$n$$$ целых чисел от $$$1$$$ до $$$n$$$, в которой все числа встречаются по одному разу. Например, (2 1 3), (1), (4 3 1 2) - перестановки, (1 2 2), (3), (1 3 2 5) - нет.
$$$^{\text{†}}$$$Циклический сдвиг массива получается перемещением последнего элемента в начало массива. У перестановки длины $$$n$$$ есть ровно $$$n$$$ циклических сдвигов.
Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 500$$$) — количество наборов входных данных.
Единственная строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$).
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите искомую перестановку. Если существует несколько решений, выведите любое из них. Если подходящих перестановок не существует, выведите $$$-1$$$.
3453
-1 4 1 3 5 2 1 3 2
Во втором примере существует перестановка, в каждом циклическом сдвиге которой есть неподвижная точка (выделено темно-красным):
Первая строка содержит номера элементов, а вторая — все сдвиги искомой перестановки.
