AT_agc025_d.[AGC025D] Choosing Points

高桥君正在研究平面上的点集。对于高桥君来说，坐标平面上的点集 $S$ 是一个好集合，当且仅当 $S$ 同时满足以下两个条件：

• $S$ 中任意两点之间的距离都不是 $\sqrt{D_1}$。
• $S$ 中任意两点之间的距离都不是 $\sqrt{D_2}$。

其中，$D_1, D_2$ 是高桥君指定的正整数常数。

现在，令 $X$ 为所有满足 $0 \leq 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 \leq x_i, y_i < 2N$。点的输出顺序不限，若存在多组解，输出任意一组均可。

限制条件

• $1 \leq N \leq 300$
• $1 \leq D_1 \leq 2 \times 10^5$
• $1 \leq D_2 \leq 2 \times 10^5$
• 输入的所有值均为整数。

样例解释 1

在本例中，两点间可能的距离只有 $2$ 和 $2\sqrt{2}$，因此确实满足条件。

由 ChatGPT 4.1 翻译