伊万将骑士放在无限的棋盘上。最初有 $$$n$$$ 骑士。如果有一个空闲单元受到至少 $$$4$$$ 骑士的攻击,那么他会在这个单元中放置新的骑士。 Ivan 重复此操作,直到没有此类空闲单元。可以证明这一过程是有限的。也可以证明,最终的位置并不取决于新骑士的排列顺序。
Ivan 要求你找到 $$$n$$$ 骑士的初始位置,这样最终至少会有 $$$\lfloor \frac{n^{2}}{10} \rfloor$$$ 骑士。
输入
输入的唯一一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^{3}$$$) — 初始位置中的骑士数量。
输出
打印 $$$n$$$ 行。每行应包含 $$$2$$$ 数字 $$$x_{i}$$$ 和 $$$y_{i}$$$ ($$$-10^{9} \le x_{i}, \,\, y_{i} \le 10^{9}$$$) — 第 $$$i$$$ 个骑士的坐标。对于所有 $$$i \ne j$$$,$$$(x_{i}, \,\, y_{i}) \ne (x_{j}, \,\, y_{j})$$$ 应该成立。换句话说,所有的骑士都应该被关在不同的牢房里。
保证解存在。
示例
输入 #1
4
输出 #1
1 1 3 1 1 5 4 4
输入 #2
7
输出 #2
2 1 1 2 4 1 5 2 2 6 5 7 6 6
注意
让我们看第二个例子:
绿色零是初始骑士。单元格 $$$(3, \,\, 3)$$$ 受到单元格 $$$(1, \,\, 2)$$$、$$$(2, \,\, 1)$$$、$$$(4, \,\, 1)$$$ 和 $$$(5, \,\, 2)$$$ 中 $$$4$$$ 骑士的攻击,因此 Ivan 将在该单元格中放置一名骑士。单元$$$(4, \,\, 5)$$$最初仅受到单元$$$(2, \,\, 6)$$$、$$$(5, \,\, 7)$$$和$$$(6, \,\, 6)$$$中$$$3$$$骑士的攻击。但是单元格 $$$(3, \,\, 3)$$$ 中的新骑士也攻击单元格 $$$(4, \,\, 5)$$$,现在它受到 $$$4$$$ 骑士的攻击,伊万将在该单元格中放置另一个骑士。没有更多的空闲单元受到 $$$4$$$ 或更多骑士的攻击,因此该过程停止。最后有$$$9$$$骑士,不少于$$$\lfloor \frac{7^{2}}{10} \rfloor = 4$$$。