Questo è un problema con doppia esecuzione. Per ogni test, la vostra soluzione verrà eseguita due volte.

Durante la lezione di informatica, Алеся e Борис studiano la crittografia. I ragazzi hanno deciso di inventare un proprio metodo per cifrare i messaggi.

Алеся sceglie $k$ interi distinti da $1$ a $n$ e indica l'insieme ottenuto con $T$. Vuole trasmettere a Борис, come messaggio, l'insieme $T$ in forma cifrata. A questo scopo, a partire dall'insieme $T$, costruirà e trasmetterà a Борис un altro insieme $R$, anch'esso formato da interi da $1$ a $n$.

I ragazzi non vogliono che la dimensione del messaggio cambi dopo la cifratura, quindi anche $R$ deve contenere esattamente $k$ numeri. Inoltre, ritengono che, se $T$ e $R$ avessero anche un solo elemento in comune, la loro cifratura non sarebbe sufficientemente sicura. Non deve quindi esistere alcun numero che appartenga sia a $T$ sia a $R$: i due insiemi devono essere disgiunti. È garantito che $k\le n/2$, quindi è sempre possibile costruire almeno un insieme $R$ a partire dall'insieme $T$.

Quando Борис riceverà il messaggio cifrato $R$, dovrà decifrarlo e ottenere il messaggio originale $T$.

Aiutate Алеся e Борис a ideare e implementare gli algoritmi di cifratura e decifratura. Nella prima esecuzione il vostro programma svolgerà il ruolo di Алеся, mentre nella seconda svolgerà quello di Борис.

Input

La prima riga dell'input contiene un numero $a$, uguale a $1$ o $2$: il numero dell'esecuzione del vostro programma.

La seconda riga contiene un numero $m$, il numero di messaggi ($1\le m\le300\,000$) che il vostro programma deve cifrare nella prima esecuzione o decifrare nella seconda.

Le successive $2m$ righe descrivono $m$ messaggi, con due righe per ciascun messaggio.

La prima riga di un messaggio contiene due interi $n_i$ e $k_i$ ($2\le n_i\le10^9$, $1\le k_i\le300\,000$, $k_i\le\frac{n_i}{2}$). La seconda riga contiene $k_i$ interi distinti da $1$ a $n_i$, in ordine crescente.

È garantito che la somma di tutti i valori $k_i$ in un test non superi $300\,000$.

Se $a=1$, i numeri dati costituiscono il messaggio originale. Se $a=2$, i numeri dati sono il risultato prodotto dal vostro programma durante la prima esecuzione per cifrare un messaggio.

Output

Il programma deve stampare $m$ righe. La $i$-esima riga deve contenere $k_i$ interi distinti da $1$ a $n_i$, in ordine crescente.

Nella prima esecuzione, per ogni messaggio originale $T_i$, il programma deve stampare un insieme $R_i$ disgiunto da $T_i$.

Nella seconda esecuzione, per ogni messaggio cifrato $R_i$, il programma deve ricostruire il messaggio originale $T_i$.

Esempi

Prima esecuzione

Input 1

1
2
2 1
1
5 2
1 4

Output 1

2
2 3

Seconda esecuzione

Input 2

2
2
5 2
2 3
2 1
2

Output 2

1 4
1

Nota

Si noti che l'esempio mostra specifiche possibilità di output nella prima esecuzione e di input nella seconda. Se il vostro programma stampa un insieme $R$ diverso, anche l'input della seconda esecuzione sarà diverso.

Inoltre, nella seconda esecuzione i messaggi cifrati non vengono necessariamente forniti al programma del concorrente nello stesso ordine della prima esecuzione.

Sottoproblemi

Per indicare i vincoli aggiuntivi sull'input, denotiamo con $t_1,t_2,\ldots,t_{k_i}$ la sequenza di numeri che costituisce l'insieme $T_i$. Questi numeri sono disposti in ordine crescente.

Denotiamo con $N$ la somma dei valori $n_i$ in un test.

Denotiamo con $K$ la somma dei valori $k_i$ in un test.