Secret Message

This is a double-run task. Your solution will be executed twice for each test case.

Alesya and Boris are studying cryptography in computer science class. They have decided to invent their own method for encrypting messages.

Alesya chooses $k$ distinct integers from $1$ to $n$ and denotes the resulting set as $T$. Alesya wants to send the set $T$ to Boris as a message in encrypted form. To do this, Alesya constructs and sends to Boris another set $R$, also consisting of integers from $1$ to $n$, based on the set $T$.

They do not want the message size to change after encryption, so $R$ must also contain exactly $k$ numbers. Furthermore, they believe that if $T$ and $R$ share at least one common element, the encryption will not be secure enough. Therefore, there should be no number that belongs to both $T$ and $R$, meaning the sets $T$ and $R$ must be disjoint. It is guaranteed that $k \leqslant n/2$, so it is always possible to construct at least one set $R$ for a given set $T$.

When Boris receives the encrypted message $R$, he must decrypt it to obtain the original message $T$.

Help Alesya and Boris design and implement the encryption and decryption algorithms. In the first run, your program will act as Alesya, and in the second run, it will act as Boris.

Input

The first line of the input contains a single integer $a$, which is $1$ or $2$ — the run number of your program.

The second line contains a single integer $m$ — the number of messages ($1 \leqslant m \leqslant 300\,000$) that your program must encrypt (in the first run) or decrypt (in the second run).

The next $2m$ lines contain the descriptions of $m$ messages, two lines per message.

The first line of each message contains two integers $n_i$ and $k_i$ ($2 \leqslant n_i \leqslant 10^9$, $1 \leqslant k_i \leqslant 300\,000$, $k_i \leqslant \frac{n_i}{2}$). The second line of each message contains $k_i$ distinct integers from $1$ to $n_i$ in increasing order.

It is guaranteed that the sum of all $k_i$ in one test does not exceed $300\,000$.

If $a = 1$, the given numbers are the original message. If $a = 2$, the given numbers are the result of your program's encryption of some message from the first run.

Output

The program must output $m$ lines, where the $i$-th line contains $k_i$ distinct integers from $1$ to $n_i$ in increasing order.

In the first run, for each original message $T_i$, the program must output a set $R_i$ that must be disjoint from $T_i$.

In the second run, for each encrypted message $R_i$, the program must recover the original message $T_i$.

Examples

Note that the example shows specific output variants for the first run and input for the second run. If your program outputs a different set $R$, the input for the second run will also be different.

Also, in the second run, the encrypted messages are not necessarily passed to the participant's program in the same order as they were in the first run.

First Run

1
2
2 1
1
5 2
1 4

Output 1

2
2 3

Second Run

2
2
5 2
2 3
2 1
2
1 4
1

Output 2

1 4
1

Subtasks

To specify additional constraints on the input data, we denote the sequence of numbers defining the set $T_i$ as $t_1, t_2, \dots, t_{k_i}$. They are arranged in increasing order. We denote the sum of $n_i$ in one test as $N$. We denote the sum of $k_i$ in one test as $K$.