Це багатопрохідна задача.

У цифрових архівах Ківотоса Плана виявила колекцію загадкових записів, відомих як Бітемпоральні Логи. Кожен лог складається з $n$ записів, пронумерованих від $1$ до $n$, які утворюють кореневе дерево. Проте структурні обмеження відрізняються залежно від того, чи є часовий потік ретроспективним (Логіка A), чи перспективним (Логіка B):

• Логіка A: Корінь дерева знаходиться в записі $1$; кожен інший запис $i$ має предка $p_i$, такого що $p_i < i$.
• Логіка B: Корінь дерева знаходиться в записі $n$; кожен інший запис $i$ має предка $q_i$, такого що $q_i > i$.

Щоб проаналізувати структурні властивості, Плана визначає два типи записів:

• Термінал (Terminal): Запис, який не є предком для жодного іншого запису.
• Вузол (Hub): Запис, який є предком для щонайменше одного іншого запису.

Плана помітила ідеальну симетрію, названу Логічним резонансом (Logical Resonance). Ця властивість виконується між логом Логіки A та логом Логіки B тоді й лише тоді, коли:

$$\text{For every } i\text{, entry } i \text{ is a Terminal in Logic A} \iff \text{entry } i \text{ is a Hub in Logic B.}$$

Плана математично довела, що кількість коректних логів Логіки A та логів Логіки B за цього обмеження є однаковою. Тепер вона доручає вам розробити Універсальний Протокол Перекладу — бієкцію — для перетворення одного формату логів на інший.

Оцінювання правильності

Ваш розв'язок запускається двічі на кожному тесті. У першому запуску ваш розв'язок має перетворити кожен лог Логіки A на лог Логіки B, що задовольняє умову Логічного резонансу. У другому запуску за даним логом Логіки B, отриманим під час вашого першого запуску, ваш розв'язок повинен точно відновити початковий лог Логіки A.

Вхідні дані другого запуску складаються з тих самих логів Логіки B, які ваш розв'язок вивів у першому запуску, можливо, в іншому порядку. Для кожного вхідного лога Логіки B у другому запуску вам потрібно вивести відповідний йому лог Логіки A. Ваш розв'язок вважається правильним, якщо для кожного такого лога Логіки B ваш вивід точно збігається з тим логом Логіки A, з якого його було згенеровано в першому запуску.

Для допомоги в розробці та тестуванні вашого розв'язку надається інструмент тестування.

Вхідні дані

Перший рядок вхідних даних містить два цілі числа $r$ ($r \in \{1, 2\}$) і $T$ ($1 \le T \le 10^5$), що позначають номер запуску та кількість наборів вхідних даних.

Для кожного набору вхідних даних перший рядок містить ціле число $n$ ($2 \le n \le 10^3$).

Якщо $r = 1$, другий рядок містить $n$ цілих чисел $p_1, p_2, \dots, p_n$, що представляють лог Логіки A. Гарантується, що $p_1 = 0$, а для $2 \le i \le n$ виконується $1 \le p_i < i$ — номер запису, до якого приєднано запис $i$. Тут ми використовуємо $0$, щоб позначити, що запис не має предка (тобто є коренем).

Інакше, якщо $r = 2$, другий рядок містить $n$ цілих чисел $q_1, q_2, \dots, q_n$, що представляють лог Логіки B. Гарантується, що $q_n = 0$, а для $1 \le i \le n - 1$ виконується $i < q_i \le n$ — номер запису, до якого приєднано запис $i$.

Гарантується, що сума $n^2$ за всіма наборами вхідних даних не перевищує $10^7$.

Вихідні дані

Якщо $r = 1$, для кожного набору вхідних даних виведіть через пробіл $n$ цілих чисел $q_1, q_2, \dots, q_n$, що представляють перетворений лог Логіки B. Має виконуватися $q_n = 0$, а для $1 \le i \le n - 1$ — нерівність $i < q_i \le n$. Також має виконуватися властивість Логічного резонансу: запис $i$ є Терміналом у Логіці A тоді й лише тоді, коли запис $i$ є Вузлом у Логіці B.

Інакше, якщо $r = 2$, для кожного набору вхідних даних виведіть через пробіл $n$ цілих чисел $p_1, p_2, \dots, p_n$, що представляють відновлений лог Логіки A.

Приклад

Приклад 1, Прохід 1

Вхідні дані

1 3
4
0 1 1 2
4
0 1 2 1
4
0 1 1 1

Вихідні дані

3 3 4 0
3 4 4 0
2 3 4 0

Приклад 1, Прохід 2

Вхідні дані

2 3
4
2 3 4 0
4
3 3 4 0
4
3 4 4 0

Вихідні дані

0 1 1 1
0 1 1 2
0 1 2 1

Пояснення до прикладу 1

Можливу коректну бієкцію показано нижче.