ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1512. Zinium

Time limit: 1.0 second
Memory limit: 64 MB

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

inputoutput
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