Это задача с многократным прохождением.

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

• Логика A: Дерево с корнем в записи $1$; каждая другая запись $i$ имеет родителя $p_i$ такого, что $p_i < i$.
• Логика B: Дерево с корнем в записи $n$; каждая другая запись $i$ имеет родителя $q_i$ такого, что $q_i > i$.

Для анализа структурных свойств Плана определяет два типа записей:

• Терминал: Запись, которая не является родителем ни для одной другой записи.
• Узел (Hub): Запись, которая является родителем по крайней мере для одной другой записи.

Плана наблюдала идеальную симметрию, называемую логическим резонансом. Это свойство выполняется между логом Логики A и логом Логики B тогда и только тогда, когда:

Для каждой записи $i$, запись $i$ является Терминалом в Логике A $\iff$ запись $i$ является Узлом в Логике 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

Пример 1 (Вывод 1)

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

Пример 2 (Проход 2)

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

Пример 2 (Вывод 2)

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

Примечание

Объяснение примера 1: Возможная допустимая биекция показана ниже.

Логика A и Логика B