配点 : $800$ 点

問題文

高橋君は平面上の点集合について研究しています。 高橋君にとって、座標平面上の点の集合 $S$ が いい集合 であるとは、$S$ が以下の条件をともに満たすことを指します。

• $S$ に属するどの $2$ 点間の距離も $\sqrt{D_1}$ でない。
• $S$ に属するどの $2$ 点間の距離も $\sqrt{D_2}$ でない。

ただし、$D_1,D_2$ は高橋君の定めた正整数の定数です。

ここで、$X$ を座標平面上の格子点 $(i,j)$ であって $0 \leq i,j < 2N$ を満たす点 $(i,j)$ 全体からなる集合としましょう。 研究者の高橋君は、$D_1,D_2$ をどのように選んでも、$X$ からうまく $N^2$ 個の点を選ぶことで、それらがいい集合をなすことを示しました。 しかし、実際にどのように選べばいい集合になるかは分かっていません。 そこで、高橋君の代わりに、$X$ のサイズ $N^2$ の部分集合であって、いい集合となるものを見つけてください。

制約

• $1 \leq N \leq 300$
• $1 \leq D_1 \leq 2 \times 10^5$
• $1 \leq D_2 \leq 2 \times 10^5$
• 入力される値は全て整数である

入力

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

$N$ $D_1$ $D_2$

出力

条件を満たすように選んだ相異なる $N^2$ 個の点を以下の形式で出力せよ。

$x_1$ $y_1$

$x_2$ $y_2$

:

$x_{N^2}$ $y_{N^2}$

ただし、$(x_i,y_i)$ は選んだ点の $i$ 番目の点を表し、$x_i,y_i$ は整数かつ $0 \leq x_i,y_i < 2N$ を満たす必要がある。 また、点はどのような順番で出力しても構わず、解が複数ある場合は、いかなるものを出力しても構わないことに注意せよ。

2 1 2

0 0
0 2
2 0
2 2

この場合 $2$ 点間の距離としてありうる値は $2$ と $2\sqrt{2}$ のみであるから、確かに条件を満たします。

3 1 5

0 0
0 2
0 4
1 1
1 3
1 5
2 0
2 2
2 4