Il s'agit d'un problème à double exécution. Pour chaque test, votre solution sera exécutée deux fois.

Pendant leur cours d'informatique, Алеся et Борис étudient la cryptographie. Ils ont décidé d'inventer leur propre méthode de chiffrement des messages.

Алеся choisit $k$ entiers distincts entre $1$ et $n$ et appelle $T$ l'ensemble obtenu. Алеся veut transmettre à Борис, comme message, l'ensemble $T$ sous forme chiffrée. Pour cela, à partir de $T$, elle construira et transmettra à Борис un autre ensemble $R$, constitué lui aussi d'entiers entre $1$ et $n$.

Ils ne veulent pas que la taille du message change après le chiffrement ; $R$ doit donc également contenir exactement $k$ nombres. Ils considèrent aussi que si $T$ et $R$ ont ne serait-ce qu'un élément commun, leur chiffrement ne sera pas assez sûr. Il ne doit donc exister aucun nombre appartenant à la fois à $T$ et à $R$ : les ensembles $T$ et $R$ doivent être disjoints. On garantit que $k \le n/2$, si bien qu'il est toujours possible de construire au moins un ensemble $R$ à partir de $T$.

Lorsque Борис recevra le message chiffré $R$, il devra le déchiffrer et retrouver le message initial $T$.

Aidez Алеся et Борис à concevoir et à implémenter des algorithmes de chiffrement et de déchiffrement. Lors de sa première exécution, votre programme jouera le rôle de Алеся, et lors de sa deuxième exécution, celui de Борис.

Entrée

La première ligne contient un nombre $a$, égal à $1$ ou à $2$ : le numéro d'exécution de votre programme.

La deuxième ligne contient un nombre $m$ : le nombre de messages ($1 \le m \le 300\,000$) que votre programme doit chiffrer (lors de la première exécution) ou déchiffrer (lors de la deuxième exécution).

Les $2m$ lignes suivantes décrivent les $m$ messages, à raison de deux lignes par message.

La première ligne d'un message contient deux entiers $n_i$ et $k_i$ ($2 \le n_i \le 10^9$, $1 \le k_i \le 300\,000$, $k_i \le \frac{n_i}{2}$). La deuxième ligne contient $k_i$ entiers distincts entre $1$ et $n_i$, dans l'ordre croissant.

On garantit que la somme de toutes les valeurs $k_i$ dans un test ne dépasse pas $300\,000$.

Si $a = 1$, les nombres donnés constituent le message initial. Si $a = 2$, les nombres donnés sont le résultat obtenu par votre programme lorsqu'il chiffre un message lors de sa première exécution.

Sortie

Le programme doit afficher $m$ lignes. La $i$-ème ligne doit contenir $k_i$ entiers distincts entre $1$ et $n_i$, dans l'ordre croissant.

Lors de la première exécution, pour chaque message initial $T_i$, le programme doit afficher un ensemble $R_i$ disjoint de $T_i$.

Lors de la deuxième exécution, pour chaque message chiffré $R_i$, le programme doit retrouver le message initial $T_i$.

Exemples

Première exécution

Entrée 1

1
2
2 1
1
5 2
1 4

Sortie 1

2
2 3

Deuxième exécution

Entrée 2

2
2
5 2
2 3
2 1
2

Sortie 2

1 4
1

Remarque

Notez que l'exemple présente des choix particuliers de sortie lors de la première exécution et d'entrée lors de la deuxième exécution. Si votre programme affiche un autre ensemble $R$, l'entrée de la deuxième exécution sera également différente.

De plus, lors de la deuxième exécution, les messages chiffrés ne sont pas nécessairement transmis au programme du participant dans l'ordre où ils figuraient lors de la première exécution.

Sous-tâches

Pour indiquer les contraintes supplémentaires sur les données d'entrée, appelons $t_1,t_2,\ldots,t_{k_i}$ la suite des nombres qui constituent l'ensemble $T_i$. Ils sont rangés dans l'ordre croissant.

Appelons $N$ la somme des $n_i$ dans un test.

Appelons $K$ la somme des $k_i$ dans un test.