[AGC025D] Choosing Points

给定 $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$

[problemUrl]: https://atcoder.jp/contests/agc025/tasks/agc025_d 高橋君は平面上の点集合について研究しています。 高橋君にとって、座標平面上の点の集合 $ 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 $ を満たす必要がある。 また、点はどのような順番で出力しても構わず、解が複数ある場合は、いかなるものを出力しても構わないことに注意せよ。

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} $ のみであるから、確かに条件を満たします。