To zadanie typu multi-pass.

W cyfrowych archiwach Kivotos, Plana odkryła kolekcję tajemniczych zapisów znanych jako Bitemporal Logs. Każdy log składa się z $n$ wpisów oznaczonych liczbami od $1$ do $n$, tworzących drzewo ukorzenione. Jednakże ograniczenia strukturalne różnią się w zależności od tego, czy przepływ czasu jest retrospektywny (Logika A), czy prospektywny (Logika B):

• Logika A: Drzewo jest ukorzenione w wpisie $1$; każdy inny wpis $i$ ma rodzica $p_i$ takiego, że $p_i < i$.
• Logika B: Drzewo jest ukorzenione w wpisie $n$; każdy inny wpis $i$ ma rodzica $q_i$ takiego, że $q_i > i$.

Aby przeanalizować właściwości strukturalne, Plana definiuje dwa typy wpisów:

• Terminal: Wpis, który nie jest rodzicem żadnego innego wpisu.
• Hub: Wpis, który jest rodzicem co najmniej jednego innego wpisu.

Plana zaobserwowała idealną symetrię zwaną Rezonansem Logicznym. Właściwość ta zachodzi między logiem Logiki A a logiem Logiki B wtedy i tylko wtedy, gdy:

Dla każdego $i$, wpis $i$ jest Terminalem w Logice A $\iff$ wpis $i$ jest Hubem w Logice B.

Plana matematycznie udowodniła, że liczba poprawnych logów Logiki A i logów Logiki B spełniających ten warunek jest identyczna. Teraz zleca Ci zaprojektowanie Uniwersalnego Protokołu Tłumaczenia — bijekcji — w celu przekształcenia jednego formatu logu w drugi.

Ocena poprawności

Twoje rozwiązanie jest wykonywane dwukrotnie w każdym teście. W pierwszym przebiegu Twoje rozwiązanie musi przekonwertować każdy log Logiki A na log Logiki B, który spełnia warunek Rezonansu Logicznego. W drugim przebiegu, mając dany log Logiki B wyprodukowany przez Twój pierwszy przebieg, Twoje rozwiązanie musi dokładnie odtworzyć oryginalny log Logiki A.

Wejście drugiego przebiegu składa się z tych samych logów Logiki B, co Twoje wyjście z pierwszego przebiegu, być może w innej kolejności. Dla każdego wejściowego logu Logiki B w drugim przebiegu musisz wypisać odpowiadający mu log Logiki A. Twoje rozwiązanie jest uznawane za poprawne, jeśli dla każdego takiego logu Logiki B Twoje wyjście jest dokładnie tym samym logiem Logiki A, który wygenerował go w pierwszym przebiegu.

Dostarczono narzędzie testujące, które pomoże Ci w tworzeniu i testowaniu rozwiązania.

Uwaga: Twoje rozwiązanie będzie oceniane jako procedura interaktywna w każdym z przebiegów.

Wejście

Pierwsza linia wejścia zawiera dwie liczby całkowite $r$ ($r \in \{1, 2\}$) oraz $T$ ($1 \le T \le 10^5$), reprezentujące numer przebiegu oraz liczbę przypadków testowych.

Dla każdego przypadku testowego pierwsza linia zawiera liczbę całkowitą $n$ ($2 \le n \le 10^3$).

Jeśli $r = 1$, druga linia zawiera $n$ liczb całkowitych $p_1, p_2, \dots, p_n$ reprezentujących log Logiki A. Gwarantuje się, że $p_1 = 0$, oraz dla $2 \le i \le n$, $1 \le p_i < i$ jest wpisem, do którego dołączony jest wpis $i$. Używamy $0$ do oznaczenia, że wpis nie ma rodzica (tj. jest korzeniem).

W przeciwnym razie, jeśli $r = 2$, druga linia zawiera $n$ liczb całkowitych $q_1, q_2, \dots, q_n$ reprezentujących log Logiki B. Gwarantuje się, że $q_n = 0$, oraz dla $1 \le i \le n - 1$, $i < q_i \le n$ jest wpisem, do którego dołączony jest wpis $i$.

Gwarantuje się, że suma $n^2$ we wszystkich przypadkach testowych nie przekracza $10^7$.

Wyjście

Jeśli $r = 1$, dla każdego przypadku testowego wypisz $n$ liczb całkowitych oddzielonych spacją, $q_1, q_2, \dots, q_n$, reprezentujących przekonwertowany log Logiki B. Musi zachodzić $q_n = 0$ oraz dla $1 \le i \le n - 1$, $i < q_i \le n$. Właściwość Rezonansu Logicznego musi być spełniona: wpis $i$ jest Terminalem w Logice A wtedy i tylko wtedy, gdy wpis $i$ jest Hubem w Logice B.

W przeciwnym razie, jeśli $r = 2$, dla każdego przypadku testowego wypisz $n$ liczb całkowitych oddzielonych spacją, $p_1, p_2, \dots, p_n$, reprezentujących odtworzony log Logiki A.

Przykład

Wejście 1 (Przebieg 1)

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

Wyjście 1 (Przebieg 1)

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

Wejście 2 (Przebieg 2)

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

Wyjście 2 (Przebieg 2)

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

Uwagi

Wyjaśnienie przykładu 1: Poniżej przedstawiono możliwą poprawną bijekcję.

Logika A Logika B