← 返回题目列表

AtCoder · agc025_d

D. 选择点

中文机器翻译题面 查看原题

分数: 800 点

问题陈述

Takahashi 正在研究平面上的点集。 高桥认为一套 坐标平面中的点的 S 是 好套装 当 S 满足以下两个条件:

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

在这里, D_1 和 D_2 是 Takahashi 指定的正整数常数。

让 X 是一组点 (i,j) 在坐标平面上,其中 i 和 j 是整数并且满足 0 ≤ i,j < 2N.

高桥已经证明,对于任何选择 D_1 和 D_2,有一种方法可以选择 N^2 点来自 X 使所选点形成一个良好的集合。 但他不知道具体如何选择这些点来组成一个好的集合。 找到一个子集 X 其尺寸为 N^2 形成了一个很好的集合。

约束

  • 1 ≤ N ≤ 300
  • 1 ≤ D_1 ≤ 2×10^5
  • 1 ≤ D_2 ≤ 2×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- 第一个选择的点。 0 ≤ x_i,y_i < 2N 必须成立,并且它们必须是整数。 可以按任何顺序打印所选点。 如果有多种可能的解决方案,您可以输出任何一个。


示例输入 1

2 1 2

示例输出 1

0 0
0 2
2 0
2 2

在这些点中,之间的距离 2 点是 2 or 2\sqrt{2},因此满足条件。


示例输入 2

3 1 5

示例输出 2

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