这是一个双重运行任务。在每个测试点上，您的程序将被运行两次。

在信息学课上，Alesya 和 Boris 正在学习密码学。他们决定发明一种加密消息的方法。

Alesya 从 $1$ 到 $n$ 中选择 $k$ 个不同的整数，并将得到的集合记为 $T$。Alesya 想要以加密形式将集合 $T$ 作为消息发送给 Boris。为此，Alesya 将根据集合 $T$ 构建并发送给 Boris 另一个同样由 $1$ 到 $n$ 之间的整数组成的集合 $R$。

他们不希望加密后消息的大小发生变化，因此 $R$ 也必须包含恰好 $k$ 个数字。此外，他们认为如果 $T$ 和 $R$ 包含至少一个公共元素，那么加密就不够可靠。因此，不存在一个既属于 $T$ 又属于 $R$ 的数字，即集合 $T$ 和 $R$ 不能有交集。保证 $k \leqslant n/2$，因此对于集合 $T$，总是可以构建至少一个集合 $R$。

当 Boris 收到加密消息 $R$ 时，他需要对其进行解密并获得原始消息 $T$。

请帮助 Alesya 和 Boris 设计并实现加密和解密算法。在第一次运行中，您的程序将扮演 Alesya 的角色，而在第二次运行中，将扮演 Boris 的角色。

输入格式

输入的第一行包含一个整数 $a$，等于 $1$ 或 $2$ —— 表示您程序的运行编号。

第二行包含一个整数 $m$ —— 您需要加密（在第一次运行中）或解密（在第二次运行中）的消息数量 ($1 \leqslant m \leqslant 300\,000$)。

接下来的 $2m$ 行包含 $m$ 条消息的描述，每条消息占两行。

每条消息的第一行包含两个整数 $n_i$ 和 $k_i$ ($2 \leqslant n_i \leqslant 10^9, 1 \leqslant k_i \leqslant 300\,000, k_i \leqslant \frac{n_i}{2}$)。第二行包含 $k_i$ 个不同的整数，范围在 $1$ 到 $n_i$ 之间，按升序排列。

保证单个测试中所有 $k_i$ 的总和不超过 $300\,000$。

如果 $a = 1$，则给定的数字是原始消息。如果 $a = 2$，则给定的数字是您的程序在第一次运行中加密某条消息后的结果。

输出格式

程序必须输出 $m$ 行，第 $i$ 行应包含 $k_i$ 个不同的整数，范围在 $1$ 到 $n_i$ 之间，按升序排列。

在第一次运行中，对于每条原始消息 $T_i$，程序必须输出一个与 $T_i$ 无交集的集合 $R_i$。

在第二次运行中，程序必须为每条加密消息 $R_i$ 恢复原始消息 $T_i$。

说明

请注意，示例中给出了第一次运行输出和第二次运行输入的具体变体。如果您的程序输出了不同的集合 $R$，则第二次运行的输入也会不同。

此外，在第二次运行中，加密消息传递给参赛者程序的顺序不一定与第一次运行时的顺序相同。

样例

输入 1

1
2
5 2
1 4
2 2
2 3

输出 1

2 3
1 4

输入 2

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

输出 2

1 4
2 3

子任务

为了指定对输入数据的额外限制，我们将定义集合 $T_i$ 的数字序列为 $t_1, t_2, \dots, t_{k_i}$，它们按升序排列。 记单个测试中 $n_i$ 的总和为 $N$。 记单个测试中 $k_i$ 的总和为 $K$。