题目描述

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

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

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

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

输入格式

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

$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\ ≦\ x_i,y_i\ <\ 2N$ を満たす必要がある。 また、点はどのような順番で出力しても構わず、解が複数ある場合は、いかなるものを出力しても構わないことに注意せよ。

题目大意

给定 $n, D_1,D_2$ , 要求构造一个在 $2n\times 2n$ 的网格中选出 $n^2$ 个点的方案, 使得任意两点间的距离不为 $\sqrt {D_1}$ 或 $\sqrt {D_2}$.

$n\leqslant 300, D\leqslant 2\times 10^5$

2 1 2

0 0
0 2
2 0
2 2

3 1 5

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

提示

制約

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

Sample Explanation 1

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