题目描述

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

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

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

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

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

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

输入格式

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

$N$

输出格式

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

$K$ $x_1$ $y_1$ $x_2$ $y_2$ $:$ $x_K$ $y_K$

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

题目大意

题目描述

有一个 $n \times n$ 的棋盘，其左上角的格子坐标为 $(0,0)$。将距离最上边 $i$ 个正方形，距最左边 $j$ 个正方形的格子记为 $(i,j)$。

对于每个横纵坐标之和为偶数的格子，将其涂黑。其余格均为白色。

请再将 $k$ 个格子涂黑，使得从左上角出发，可以通过反复移动到当前格子的四连通黑块来到达其他任意一个黑格。

输入格式

一行一个整数 $n$。（$1\le n\le 1000$）

输出格式

第一行输出整数 $k$。$k$ 是不大于十七万的自然数。

第二行开始的 $k$ 行，每行输出一个新涂黑黑格的横纵坐标。每个格子之前都未被涂黑过且坐标合法方可通过。

2

1
1 0

4

3
0 1
2 1
2 3

提示

制約

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

判定

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

• $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)$
• 出力された全てのマスを黒く塗ることで問題文中の条件が達成されている。