CF1067C.Knights

Ivan places knights on infinite chessboard. Initially there are $n$ knights. If there is free cell which is under attack of at least $4$ knights then he places new knight in this cell. Ivan repeats this until there are no such free cells. One can prove that this process is finite. One can also prove that position in the end does not depend on the order in which new knights are placed.

Ivan asked you to find initial placement of exactly $n$ knights such that in the end there will be at least $\lfloor \frac{n^{2}}{10} \rfloor$ knights.

伊万在无限大的棋盘上放置骑士。初始时有 $n$ 个骑士。若存在一个空闲格子，且该格子至少受到 $4$ 个骑士的攻击，则他在该格子中放置一个新的骑士。伊万不断重复此过程，直到不存在满足条件的空闲格子为止。可以证明该过程是有限的；也可以证明最终的棋盘布局与新增骑士的放置顺序无关。

伊万请你找出一种恰好放置 $n$ 个骑士的初始布局，使得最终棋盘上的骑士总数至少为 $\lfloor \frac{n^{2}}{10} \rfloor$。

The only line of input contains one integer $n$ ($1 \le n \le 10^{3}$) — number of knights in the initial placement.

输入仅包含一行，其中有一个整数 $n$（$1 \le n \le 10^{3}$）——初始摆放的骑士数量。

Print $n$ lines. Each line should contain $2$ numbers $x_{i}$ and $y_{i}$ ($-10^{9} \le x_{i}, \,\, y_{i} \le 10^{9}$) — coordinates of $i$-th knight. For all $i \ne j$, $(x_{i}, \,\, y_{i}) \ne (x_{j}, \,\, y_{j})$ should hold. In other words, all knights should be in different cells.

It is guaranteed that the solution exists.

输出 $n$ 行。每行应包含两个数 $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})$。换言之，所有骑士必须位于互不相同的格子中。

保证解存在。

Let's look at second example:

Green zeroes are initial knights. Cell $(3, \,\, 3)$ is under attack of $4$ knights in cells $(1, \,\, 2)$, $(2, \,\, 1)$, $(4, \,\, 1)$ and $(5, \,\, 2)$, therefore Ivan will place a knight in this cell. Cell $(4, \,\, 5)$ is initially attacked by only $3$ knights in cells $(2, \,\, 6)$, $(5, \,\, 7)$ and $(6, \,\, 6)$. But new knight in cell $(3, \,\, 3)$ also attacks cell $(4, \,\, 5)$, now it is attacked by $4$ knights and Ivan will place another knight in this cell. There are no more free cells which are attacked by $4$ or more knights, so the process stops. There are $9$ knights in the end, which is not less than $\lfloor \frac{7^{2}}{10} \rfloor = 4$.

我们来看第二个例子：

绿色的零表示初始放置的骑士。格子 $(3, \,\, 3)$ 受到位于 $(1, \,\, 2)$、$(2, \,\, 1)$、$(4, \,\, 1)$ 和 $(5, \,\, 2)$ 这四个格子中的骑士的攻击，因此伊万将在该格子中再放置一名骑士。格子 $(4, \,\, 5)$ 最初仅受到位于 $(2, \,\, 6)$、$(5, \,\, 7)$ 和 $(6, \,\, 6)$ 这三个格子中的骑士的攻击；但新放置在 $(3, \,\, 3)$ 的骑士也会攻击格子 $(4, \,\, 5)$，因此该格子现在共受到 $4$ 名骑士的攻击，伊万将在该格子中再放置一名骑士。此时已不存在其他空闲格子被 $4$ 名或更多骑士攻击，因此该过程终止。最终共有 $9$ 名骑士，不少于 $\lfloor \frac{7^{2}}{10} \rfloor = 4$。