ストーリー

マンハッタンに住んでいるオスバチ忍者のチェリーくんはドローンを飛ばすことを趣味にしています. 今日もチェリーくんはいろんな所へ向かってドローンを飛ばしてます.

充電が切れないようにするためにも, 空よりも高いところにいるチェリーくんにアドバイスしてあげましょう.

問題文

$xy$ 上の正方形領域 $R$ を $R:=\{(x,y) \mid 0 \leq x \leq L, 0 \leq y \leq L\}$ で定める. この $R$ 内をドローンが飛行する.

$R$ 内には $N$ 個のチェックポイントがあり, $i~(1 \leq i \leq N)$ 番目のチェックポイント $P_i$ は座標 $(X_i, Y_i)$ にある.

ここで, $xy$ 平面上の $2$ つの点 $S=(x,y), S'=(x', y')$ において, $S$ から $S'$ へドローンが移動するために必要なコスト $\operatorname{cost}(S,S')$ は $$\operatorname{cost}(S,S')=\lvert x-x' \rvert+\lvert y-y' \rvert $$ である.

以下を満たすような $R$ 内の点の列 $A=(A_1, A_2, \dots, A_M)$ の一例を挙げよ.

• $1 \leq M \leq 2N$.
• $A_j$ の $x$ 座標, $y$ 座標は共に整数である $\quad (1 \leq j \leq M)$.
• $A_j \in R \quad (j=1,2, \dots, M)$.
• $A_1, A_2, \dots, A_M$ の中に, $P_i$ が $1$ 回以上現れる $\quad (1 \leq i \leq N)$.
• $A_1 \to A_2 \to \dots \to A_{M-1} \to A_M \to A_1$ の順にドローンが移動するとき, コストの総和は $1000 L$ 以下である.つまり, $$\sum_{j=1}^{M-1} \operatorname{cost} (A_j, A_{j+1})+\operatorname{cost}(A_M, A_1) \leq 1000L$$ である.

なお, この問題の制約下では, 正解となるような $A$ が存在することが証明できる.

$T$ 個のテストケースについて答えよ.

制約

• $1 \leq T \leq 10^5$.
• 各テストケースに関する制約.
• $2 \leq N \leq 2 \times 10^5$.
• $1 \leq L \leq 10^9$
• $0 \leq X_i \leq L, 0 \leq Y_i \leq L \quad (1 \leq i \leq N)$.
• $i \neq j \Rightarrow (X_i, Y_i) \neq (X_j, Y_j) \quad (1 \leq i \leq N, 1 \leq j \leq N)$.
• テストファイルに関する制約.
  • $T$ 個のテストケースにおける $N$ の総和は $2 \times 10^5$ 以下である.
• 入力は全て整数である.

入力

$T$
${\rm Testcase}_1$
${\rm Testcase}_2$
$\vdots$
${\rm Testcase}_T$

$N$ $L$
$X_1$ $Y_1$
$X_2$ $Y_2$
$\vdots$
$X_N$ $Y_N$

出力

各テストケースについて, 解答する $A=(A_1,A_2, \dots, A_M)$ において, $A_j$ の座標を $(x_j, y_j)$ とするとき, 以下の形式で出力せよ.

$M$
$x_1$ $y_1$
$x_2$ $y_2$
$\vdots$
$x_M$ $y_M$

サンプル

2
4 6
0 1
4 2
5 3
3 1
3 1000000000
0 0
1000000000 0
1000000000 1000000000

7
3 5
0 1
2 6
5 3
3 1
4 2
1 4
5
0 0
0 1000000000
1000000000 1000000000
1000000000 0
1000000000 1000000000