Боб является страстным поклонником видеоигры «League of Leesins», и сегодня он празднует то, что подходит к концу Чемпионат мира League of Leesins!

В турнире приняли участие $$$n$$$ ($$$n \ge 5$$$) команд по всему миру. Перед началом турнира Боб сделал прогноз рейтинга каждой команды от $$$1$$$ до $$$n$$$. После финала он сравнил прогноз с фактическим результатом и обнаружил, что $$$i$$$-я команда в соответствии с его прогнозом оказалась на $$$p_i$$$-й позиции ($$$1 \le p_i \le n$$$, все $$$p_i$$$ различны). Другими словами, $$$p$$$ является перестановкой чисел $$$1, 2, \dots, n$$$.

Поскольку любимый игрок Боба в Лиге — знаменитый «3ga», он решил записать каждые $$$3$$$ последовательные элементы перестановки $$$p$$$. Формально Боб создал массив $$$q$$$ из $$$n-2$$$ троек, где $$$q_i = (p_i, p_{i+1}, p_{i+2})$$$ для каждого $$$1 \le i \le n-2$$$. Боб очень гордился своим набором, поэтому он показал его своей подруге Алисе.

Узнав о массиве Боба, Алиса заявила, что может найти перестановку $$$p$$$, даже если Боб переставит (перемешает) элементы $$$q$$$ и элементы в каждой тройке. Конечно, Боб не поверил в такую магию, поэтому он сделал то, что и сказала, чтобы увидеть, что она ему скажет.

Например, если $$$n = 5$$$ и $$$p = [1, 4, 2, 3, 5]$$$, тогда массив $$$q$$$ будет равен $$$[(1, 4, 2), (4, 2, 3), (2, 3, 5)]$$$. Боб может перемешать сами тройки и числа в тройках, чтобы получить $$$[(4, 3, 2), (2, 3, 5), (4, 1, 2)]$$$. Обратите внимание, что $$$[(1, 4, 2), (4, 2, 2), (3, 3, 5)]$$$ — неправильная перестановка $$$q$$$, так как Боб не может менять местами числа между тройками.

Как друг Алисы, вы точно знаете, что Алиса просто пыталась похвастаться, поэтому вы решили ее спасти, дав ей любую перестановку $$$p$$$, которая соответствует массиву $$$q$$$, который ей дали.