Knights

Description:

Input:

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

Output:

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.

Sample Input:

4

Sample Output:

1 1
3 1
1 5
4 4

Sample Input:

7

Sample Output:

2 1
1 2
4 1
5 2
2 6
5 7
6 6

Note:

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$$$.