これは二度実行される問題です。各テストで、あなたの解答は二度実行されます。

情報の授業で、Алеся と Борис は暗号について学んでいます。二人はメッセージを暗号化する独自の方法を考えることにしました。

Алеся は $1$ から $n$ までの相異なる整数を $k$ 個選び、その集合を $T$ とします。Алеся は集合 $T$ をメッセージとして、暗号化した形で Борис に送りたいと考えています。そのために、Алеся は集合 $T$ から、同じく $1$ から $n$ までの整数で構成される別の集合 $R$ を作り、Борис に送ります。

二人は暗号化によってメッセージの大きさが変わらないようにしたいので、$R$ もちょうど $k$ 個の数を含まなければなりません。また、$T$ と $R$ に共通の要素が一つでもあると、暗号は十分に安全でないと考えています。したがって、$T$ と $R$ の両方に含まれる数があってはいけません。つまり、集合 $T$ と $R$ は互いに素でなければなりません。$k \le n/2$ が保証されるので、集合 $T$ に対して集合 $R$ を少なくとも一つ作ることは常に可能です。

Борис は暗号化されたメッセージ $R$ を受け取ったら、それを復号して元のメッセージ $T$ を得なければなりません。

Алеся と Борис が暗号化と復号のアルゴリズムを考え、実装するのを手伝ってください。あなたのプログラムは、最初の実行では Алеся の役割を、二度目の実行では Борис の役割を果たします。

入力

入力の最初の行には、あなたのプログラムの実行番号を表す、$1$ または $2$ に等しい数 $a$ が一つ与えられます。

二行目には、あなたのプログラムが暗号化（最初の実行）または復号（二度目の実行）しなければならないメッセージの個数 $m$ が一つ与えられます（$1 \le m \le 300\,000$）。

続く $2m$ 行には、各メッセージにつき二行ずつ、$m$ 個のメッセージの記述が与えられます。

メッセージの最初の行には、二つの整数 $n_i$ と $k_i$ が書かれています（$2 \le n_i \le 10^9$、$1 \le k_i \le 300\,000$、$k_i \le \frac{n_i}{2}$）。メッセージの二行目には、$1$ から $n_i$ までの相異なる整数 $k_i$ 個が昇順で書かれています。

一つのテストにおけるすべての $k_i$ の値の合計は $300\,000$ 以下であることが保証されます。

$a = 1$ の場合、これらの数は元のメッセージです。$a = 2$ の場合、これらの数は、最初の実行であなたのプログラムが何らかのメッセージを暗号化した結果です。

出力

プログラムは $m$ 行を出力しなければなりません。$i$ 行目には、$1$ から $n_i$ までの相異なる整数 $k_i$ 個を昇順で出力してください。

最初の実行では、各元のメッセージ $T_i$ に対して、$T_i$ と互いに素な集合 $R_i$ を出力しなければなりません。

二度目の実行では、各暗号化されたメッセージ $R_i$ に対して、元のメッセージ $T_i$ を復元しなければなりません。

入出力例

最初の実行

入力 1

1
2
2 1
1
5 2
1 4

出力 1

2
2 3

二度目の実行

入力 2

2
2
5 2
2 3
2 1
2

出力 2

1 4
1

注記

例では、最初の実行の出力と二度目の実行の入力について、具体的な一つの選び方を示していることに注意してください。あなたのプログラムが異なる集合 $R$ を出力した場合、二度目の実行の入力も異なります。

また、二度目の実行で参加者のプログラムに渡される暗号化されたメッセージの順序は、最初の実行での順序と同じとは限りません。

小課題

入力に対する追加の制約を示すため、集合 $T_i$ を構成する数の列を $t_1, t_2, \ldots, t_{k_i}$ とします。これらは昇順に並んでいます。

一つのテストにおける $n_i$ の合計を $N$ とします。

一つのテストにおける $k_i$ の合計を $K$ とします。