目前Tiny正在学习计算几何。当试图解决一个名为“平面上最接近的点对”的问题时,他发现给出错误时间复杂度的代码被接受,而不是超过时间限制。
问题如下。给定平面上的 n 个点,找到一对距离最小的点。 (x1, y1) 和 (x2, y2) 之间的距离为 $$\sqrt{(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}}$$。
意外代码的伪代码如下:
这里,tot可以看作是代码的运行时间。由于计算机每秒只能运行有限数量的操作,因此 tot 不应超过 k,以免超出时间限制。
你是一位伟大的黑客。您能帮Tiny生成一个测试数据并让代码得到Time Limit Exceeded吗?
输入
单行,包含两个空格分隔的整数 n 和 k (2 ≤ n ≤ 2000, 1 ≤ k ≤ 109)。
输出
如果不存在让给定代码获得 TLE 的数据,则打印“无解”(不带引号); else 打印n行,第i行包含两个整数xi,yi (|xi|, |yi| ≤ 109),代表第i个点的坐标。
必须满足以下条件:
- 所有点必须不同。
- |xi|, |yi| ≤ 109。
- 运行给定代码后,tot 的值应大于 k。
示例
输入 #1
4 3
输出 #1
0 0 0 1 1 0 1 1
输入 #2
2 100
输出 #2
no solution