Есть ряд из \(n\) кошек, пронумерованных с \(1\) по \(n\): \(i\)-я кошка на позиции \(i\). Кошкам надоедает вращаться на одном и том же месте целый день, поэтому они хотят поменяться местами так, чтобы никакая кошка не осталась на том же самом месте. Кошки очень ленивы, а поэтому они хотят минимизировать суммарное расстояние, на которое им нужно передвинуться. Помогите им решить, какой кошке переместиться на какое место.
Например, если кошки \(3\), то можно выбрать следующую перестановку: \([3, 1, 2]\). Никакая кошка не осталась на своем месте. Суммарное расстояние, на которое сдвинулись кошки равно \(1 + 1 + 2 = 4\), т. е. кошка \(1\) сдвинулась на один вправо, кошка \(2\) сдвинулась на один вправо, а кошка \(3\) — на два влево.
Выходные данные
Выведите \(t\) ответов — по одному на набор входных данных. Каждый ответ должен состоять из \(n\) целых чисел — перестановки минимальной стоимости. Если существует несколько ответов, выведите любой из них.
Примечание
В первом наборе входных данных есть одна возможная перестановка, удовлетворяющая условиям: \([2, 1]\).
Второй набор описан в условии задачи. Другой возможный ответ — это \([2, 3, 1]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
2
3
|
2 1
3 1 2
|