配点 : $600$ 点

問題文

$1$ から $N$ までの番号のついた $N$ 個の整数の組 $(x_i,y_i)$ と、整数 $K$ が与えられます。 以下の条件を満たす整数の組 $(p,q)$ を「出力」で指定する形式に従ってすべて列挙してください。

• $1 \le p < q \le N$
• $\sqrt{(x_p-x_q)^2+(y_p-y_q)^2} \le K$

ただし、そのような整数の組が $4 \times 10^5$ 組以下であることは保証されます。

制約

• 入力はすべて整数
• $1 \le N \le 2 \times 10^5$
• $1 \le K \le 1.5 \times 10^9$
• $0 \le x_i,y_i \le 10^9$
• 列挙すべき整数の組は $4 \times 10^5$ 組以下である

入力

入力は以下の形式で標準入力から与えられる。

$N$ $K$

$x_1$ $y_1$

$x_2$ $y_2$

$\vdots$

$x_N$ $y_N$

出力

以下の形式で出力せよ。

$M$

$p_1$ $q_1$

$p_2$ $q_2$

$\vdots$

$p_M$ $q_M$

まず、 $1$ 行目に整数 $M$ を出力せよ。 $M$ は出力する整数の組の個数を表す。 続く $M$ 行に、列挙するべき整数の組 $(p_i,q_i)$ を $1$ 行に $1$ つずつ空白区切りで、 辞書順で 出力せよ。 ただし、整数の組 $(a,b),(c,d)$ が以下の条件のどちらかを満たすとき、またその時に限り、 整数の組 $(a,b)$ が整数の組 $(c,d)$ より辞書順で前であるとする。

• $a である。
• $a=c$ であり、かつ $b である。

6 5
2 0
2 2
3 4
0 0
5 5
8 3

9
1 2
1 3
1 4
2 3
2 4
2 5
3 4
3 5
5 6

条件を満たす整数の組は以下の $9$ 個なので、これを出力形式に従って出力して下さい。 $(1,2),(1,3),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(5,6)$

2 1414213562
0 0
1000000000 1000000000

0

条件を満たす整数の組が $0$ 組である場合もあります。

10 150
300 300
300 400
300 500
400 300
400 400
400 400
400 500
500 300
500 400
500 500

29
1 2
1 4
1 5
1 6
2 3
2 4
2 5
2 6
2 7
3 5
3 6
3 7
4 5
4 6
4 8
4 9
5 6
5 7
5 8
5 9
5 10
6 7
6 8
6 9
6 10
7 9
7 10
8 9
9 10

$x_i=x_j$ かつ $y_i=y_j$ であるような整数の組 $(i,j)$ ($i < j$) が存在する場合もあります。