配点 : $100$ 点

問題文

$N$ マス × $N$ マスのチェスボードがあります。

最も左上のマスから、右に $i$ マス、下に $j$ マス進んだマスを $(i, j)$ と呼びます。特に、最も左上のマスは $(0, 0)$ です。

$i+j$ が偶数であるようなマス $(i, j)$ は黒、それ以外のマスは白で塗られています。

これから、いくつかの白いマスを黒に塗り替えることで以下の条件が満たされるようにします。

• マス $(0, 0)$ から始めて、辺を共有する黒いマスに移動するという操作を繰り返したときに、全ての黒いマスにたどり着くことができる。

$170000$ 個以下のマスを黒く塗り替えることで条件を達成してください。

制約

• $1 \leq N \leq 1,000$

入力

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

$N$

出力

条件を達成するために黒く塗り替えたマスの情報を以下の形式で出力せよ。

$K$

$x_1$ $y_1$

$x_2$ $y_2$

$:$

$x_K$ $y_K$

これは、全部で $K$ 個のマスを黒く塗り替えており、$i$ 番目に $(x_i, y_i)$ のマスを黒く塗り替えたことを表す。

判定

以下の全ての条件を満たしているときのみ、その出力は正解とみなされる。

• $0 \leq K \leq 170000$
• $0 \leq x_i, y_i \leq N-1$
• 全ての $i$ に対して $x_i + y_i$ は奇数。
• $i \neq j$ ならば $(x_i, y_i) \neq (x_j, y_j)$
• 出力された全てのマスを黒く塗ることで問題文中の条件が達成されている。

2

1
1 0

4

3
0 1
2 1
2 3