In a far away country there are N cities, and every two of them are connected by a two-way direct airplane line. Gripped by the crisis, the airline company has decided to remove as many lines as possible.

The lines will be eliminated one by one. This elimination must not significantly affect the city connections, so when removing a line, it must belong to a cycle of length four. In other words, if the cities A, B, C, D are such that currently there are lines AB, BC, CD and DA, then we can remove any of these lines.

It is possible to prove that there must remain at least N lines at the end of the elimination process (i.e., that we are unable to remove more lines under the described conditions). You are not required to prove it, but to write a program that helps the airline company to remove a line by line until there are exactly N left.

Input

4 ≤ N ≤ 2000.

Output

Print one line of data for each airplane line you are removing.

In each of these lines, print the numbers A, B, C, D which represent the cities forming a cycle. These numbers indicate that you are removing the line AB.

Example

input
4
output

2 3 1 4
3 4 2 1


input

5
output

3 4 5 2
2 3 1 5
3 5 2 1
2 4 1 5
4 5 2 1