Боб является страстным поклонником видеоигры «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\), который ей дали.