REMOVE - Help the Airline Company

no tags 

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

hide comments
arbit: 2016-03-27 10:57:02

I am getting "SIGXFSZ" error when I submit my solution. When I look it up, it says that this is thrown when file size limit is exceeded. Could you please look into this? The file size for maximum input of 2000 seems to be around 40MB.


Added by:Adrian Satja Kurdija
Date:2011-10-30
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:originated from a mathematical problem