---
# System prepended metadata

title: ROI 23 Secret Message
tags: [statement]

---

# ROI 23 Secret Message
https://www.acmicpc.net/problem/28430

This is a communication problem. On each test, your solution will be run twice.

In a computer science class, Alesya and Boris are learning about cryptography. They decided to invent their own method for encrypting messages.

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

The students don't want the size of the message to change after encryption, so $R$ must also contain exactly $k$ numbers. Moreover, they believe that if $T$ and $R$ have at least one common element, their encryption will be insufficiently secure. Thus, no number should belong to both $T$ and $R$. It is guaranteed that $k \leq \frac{n}{2}$, so it is always possible to construct at least one set $R$ from $T$.

When Boris receives the encrypted message $R$, he needs to decrypt it and retrieve the original message $T$.

Help Alesya and Boris devise and implement the encryption and decryption algorithms. During the first run, your program will act as Alesya, and during the second run, as Boris.

## Input

In the first line of the input data, there is a single number $a$, equal to $1$ or $2$ — the run number of your program.

In the second line, there is a single number $m$ — the number of messages ($1 \le m \le 300,000$) that your program should encrypt (in the first run) or decrypt (in the second run).

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

In the first line of the message, there are two integers $n_i$ and $k_i$ ($2 \le n_i \le 10^9$, $1 \le k_i \le 300,000$, $k_i \le \frac{n_i}{2}$). In the second line of the message, there are $k_i$ distinct integers from $1$ to $n_i$ in ascending order.

It is guaranteed that the sum of all $k_i$ values 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 running your encryption program on some message during the first run of your program.

### Output

The program should output $m$ lines, where the $i$-th line should contain $k_i$ distinct integers from $1$ to $n_i$ in ascending order.

In the first run, for each original message $T_i$, the program should output the set $R_i$, which should not intersect with $T_i$.

In the second run, the program should restore the original message $T_i$ for each encrypted message $R_i$.

### Subtsaks

To indicate additional constraints on the input data, denote the sequence of numbers that define the set $T_i$ as $t_1, t_2, \dots, t_{k_i}$. They are arranged in ascending order.

Denote the sum of $n_i$ in one test as $N$.

Denote the sum of $k_i$ in one test as $K$.
![image](https://hackmd.io/_uploads/r1--Jtb4A.png)



## Examples

Example Input 1
```
1
2
2 1
1
5 2
1 4
```
Example Output 1
```
2
2 3
```
Example Input 2
```
2
2
5 2
2 3
2 1
2
```
Example Output 2
```
1 4
1
```
Note

Note that in the example, specific outputs for the first run and corresponding inputs for the second run are shown. If your program produces a different set $R$ in the first run, the input for the second run will also be different.

Additionally, in the second run, encrypted messages are not necessarily given to the participant's program in the order they were produced in the first run.