Questo è un problema a più passaggi (multi-pass).

Negli archivi digitali di Kivotos, Plana ha scoperto una collezione di misteriosi registri noti come Log Bitemporali. Ciascun log è costituito da $n$ voci numerate da $1$ a $n$ che formano un albero radicato. Tuttavia, i vincoli strutturali differiscono a seconda che il flusso temporale sia retrospettivo (Logica A) o prospettico (Logica B):

• Logica A: L'albero è radicato nella voce $1$; ogni altra voce $i$ ha un genitore $p_i$ tale che $p_i < i$.
• Logica B: L'albero è radicato nella voce $n$; ogni altra voce $i$ ha un genitore $q_i$ tale che $q_i > i$.

Per analizzare le proprietà strutturali, Plana definisce due tipi di voci:

• Terminale (Terminal): Una voce che non funge da genitore per nessuna altra voce.
• Snodo (Hub): Una voce che funge da genitore per almeno una altra voce.

Plana ha osservato una simmetria perfetta chiamata Risonanza Logica (Logical Resonance). Questa proprietà vale tra un log di Logica A e un log di Logica B se e solo se:

$$\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.}$$

Plana ha dimostrato matematicamente che il numero di log validi di Logica A e di Logica B sotto questo vincolo è identico. Ora ti incarica di progettare un Protocollo di Traduzione Universale — una biiezione — per trasformare un formato di log nell'altro.

Valutazione della Correttezza

La tua soluzione viene eseguita due volte su ciascun test. Nella prima esecuzione, la tua soluzione deve convertire ciascun log di Logica A in un log di Logica B che soddisfi la condizione di Risonanza Logica. Nella seconda esecuzione, dato un log di Logica B prodotto dalla tua prima esecuzione, la tua soluzione deve ricostruire esattamente il log di Logica A originale.

L'input della seconda esecuzione consiste negli stessi log di Logica B prodotti in output dalla prima esecuzione, eventualmente in un ordine diverso. Per ciascun log di Logica B in input nella seconda esecuzione, devi stampare il corrispondente log di Logica A. La tua soluzione è considerata corretta se, per ogni tale log di Logica B, il tuo output coincide esattamente con il log di Logica A che lo ha generato nella prima esecuzione.

È fornito uno strumento di test per aiutarti a sviluppare e testare la tua soluzione.

Input

La prima riga dell'input contiene due interi $r$ ($r \in \{1, 2\}$) e $T$ ($1 \le T \le 10^5$), che rappresentano il numero dell'esecuzione e il numero di casi di test.

Per ciascun caso di test, la prima riga contiene un intero $n$ ($2 \le n \le 10^3$).

Se $r = 1$, la seconda riga contiene $n$ interi $p_1, p_2, \dots, p_n$ che rappresentano il log di Logica A. È garantito che $p_1 = 0$ e, per $2 \le i \le n$, $1 \le p_i < i$ è la voce a cui è collegata la voce $i$. Qui usiamo $0$ per indicare che una voce non ha genitore (ossia è la radice).

Altrimenti, se $r = 2$, la seconda riga contiene $n$ interi $q_1, q_2, \dots, q_n$ che rappresentano il log di Logica B. È garantito che $q_n = 0$ e, per $1 \le i \le n - 1$, $i < q_i \le n$ è la voce a cui è collegata la voce $i$.

È garantito che la somma di $n^2$ su tutti i casi di test non superi $10^7$.

Output

Se $r = 1$, per ciascun caso di test stampa $n$ interi separati da uno spazio, $q_1, q_2, \dots, q_n$, che rappresentano il log di Logica B convertito. Deve valere $q_n = 0$ e, per $1 \le i \le n - 1$, $i < q_i \le n$. Deve valere la proprietà di Risonanza Logica: la voce $i$ è un Terminale nella Logica A se e solo se la voce $i$ è uno Snodo nella Logica B.

Altrimenti, se $r = 2$, per ciascun caso di test stampa $n$ interi separati da uno spazio, $p_1, p_2, \dots, p_n$, che rappresentano il log di Logica A ricostruito.

Esempio

Esempio 1, Passaggio 1

Input

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

Output

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

Esempio 1, Passaggio 2

Input

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

Output

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

Spiegazione dell'Esempio 1

Una possibile biiezione valida è mostrata di seguito.