Background
Zinium is a miracle of our world - and probably of all the worlds. Found at the close of the XIX-th century during archeological dig on the territory of modern Albania, Zinium belonged to Caesar himself and was lost in his last campaign.
Problem
The artifact is a chessboard of N*N cells in size. A cell in its left-bottom corner has coordinates (1, 1) and a cell in its right-top corner has coordinates (N, N). The legend says if one could place N queens onto the board in such a way, that none of them attacks the other, released energy of Zinium will change the world beyond recognition. Rivers will turn back, the sky will fall onto the earth, people will learn to call things by their proper names... Petr the Gorgeous himself will probably participate in the Fourth Challenge of Timus Top Coders... Or will not. So, it is high time to check it.
Input
The only line contains the integer number N (4 ≤ N ≤ 100000).
Output
For each queen you should output the coordinates of its cell on a separate line. The coordinates should be separated by single spaces. The queens may be listed in any order. If the problem has several solutions, you should output any of them.
Sample
input | output |
---|
8
| 1 5
2 1
3 8
4 4
5 2
6 7
7 3
8 6
|
Notes
Two queens attack themselves, if they are placed in the cells positioned on the same horizontal, vertical or diagonal line.
Problem Author: Ilya Grebnov, Nikita Rybak, Dmitry Kovalioff
Problem Source: Timus Top Coders: Third Challenge