Dies ist eine Aufgabe mit zwei Programmläufen. Für jeden Test wird Ihre Lösung zweimal ausgeführt.

Im Informatikunterricht beschäftigen sich Алеся und Борис mit Kryptografie. Die beiden haben beschlossen, ihr eigenes Verfahren zur Verschlüsselung von Nachrichten zu erfinden.

Алеся wählt $k$ verschiedene ganze Zahlen von $1$ bis $n$ und bezeichnet die entstandene Menge mit $T$. Sie möchte Борис die Menge $T$ als verschlüsselte Nachricht übermitteln. Dazu konstruiert sie aus der Menge $T$ eine andere Menge $R$, die ebenfalls aus ganzen Zahlen von $1$ bis $n$ besteht, und übermittelt diese an Борис.

Die beiden möchten nicht, dass sich die Größe einer Nachricht durch die Verschlüsselung verändert. Deshalb muss auch $R$ genau $k$ Zahlen enthalten. Außerdem halten sie die Verschlüsselung für nicht sicher genug, wenn $T$ und $R$ auch nur ein gemeinsames Element enthalten. Daher darf es keine Zahl geben, die sowohl in $T$ als auch in $R$ liegt; die Mengen $T$ und $R$ müssen also disjunkt sein. Es ist garantiert, dass $k \le n/2$ gilt, sodass sich zu jeder Menge $T$ stets mindestens eine solche Menge $R$ konstruieren lässt.

Wenn Борис die verschlüsselte Nachricht $R$ erhält, muss er sie entschlüsseln und die ursprüngliche Nachricht $T$ wiederherstellen.

Helfen Sie Алеся und Борис, Algorithmen zur Verschlüsselung und Entschlüsselung zu entwickeln und zu implementieren. Beim ersten Lauf übernimmt Ihr Programm die Rolle von Алеся, beim zweiten Lauf die Rolle von Борис.

Eingabe

Die erste Eingabezeile enthält eine Zahl $a$, die entweder $1$ oder $2$ ist und die Nummer des Programmlaufs angibt.

Die zweite Zeile enthält eine Zahl $m$, die Anzahl der Nachrichten ($1 \le m \le 300\,000$), die Ihr Programm im ersten Lauf verschlüsseln beziehungsweise im zweiten Lauf entschlüsseln muss.

Die folgenden $2m$ Zeilen beschreiben die $m$ Nachrichten, mit jeweils zwei Zeilen pro Nachricht.

Die erste Zeile einer Nachricht enthält zwei ganze Zahlen $n_i$ und $k_i$ ($2 \le n_i \le 10^9$, $1 \le k_i \le 300\,000$, $k_i \le \frac{n_i}{2}$). Die zweite Zeile der Nachricht enthält $k_i$ verschiedene ganze Zahlen von $1$ bis $n_i$ in aufsteigender Reihenfolge.

Es ist garantiert, dass die Summe aller Werte $k_i$ in einem Test höchstens $300\,000$ beträgt.

Falls $a=1$ ist, bilden die angegebenen Zahlen die ursprüngliche Nachricht. Falls $a=2$ ist, sind sie das Ergebnis, das Ihr Programm beim Verschlüsseln einer Nachricht im ersten Lauf erzeugt hat.

Ausgabe

Ihr Programm muss $m$ Zeilen ausgeben. Die $i$-te Zeile muss $k_i$ verschiedene ganze Zahlen von $1$ bis $n_i$ in aufsteigender Reihenfolge enthalten.

Im ersten Lauf muss das Programm zu jeder ursprünglichen Nachricht $T_i$ eine Menge $R_i$ ausgeben, die mit $T_i$ disjunkt ist.

Im zweiten Lauf muss das Programm aus jeder verschlüsselten Nachricht $R_i$ die ursprüngliche Nachricht $T_i$ wiederherstellen.

Beispiele

Erster Lauf

Eingabe 1

1
2
2 1
1
5 2
1 4

Ausgabe 1

2
2 3

Zweiter Lauf

Eingabe 2

2
2
5 2
2 3
2 1
2

Ausgabe 2

1 4
1

Hinweis

Beachten Sie, dass das Beispiel konkrete Möglichkeiten für die Ausgabe im ersten Lauf und die Eingabe im zweiten Lauf zeigt. Wenn Ihr Programm eine andere Menge $R$ ausgibt, ist auch die Eingabe im zweiten Lauf anders.

Außerdem werden die verschlüsselten Nachrichten Ihrem Programm im zweiten Lauf nicht unbedingt in derselben Reihenfolge übergeben, in der sie im ersten Lauf vorkamen.

Teilaufgaben

Um zusätzliche Eingabebeschränkungen anzugeben, bezeichnen wir die Folge der Zahlen, die die Menge $T_i$ bilden, mit $t_1,t_2,\ldots,t_{k_i}$. Sie sind in aufsteigender Reihenfolge angeordnet.

Die Summe der Werte $n_i$ in einem Test bezeichnen wir mit $N$.

Die Summe der Werte $k_i$ in einem Test bezeichnen wir mit $K$.