REVSEQ - Reverse the Sequence

This is a very ad-hoc problem. Consider a sequence (N, N-1, ..., 2, 1). You have to reverse it, that is, make it become (1, 2, ..., N-1, N). And how do you do this? By making operations of the following kind.

Writing three natural numbers A, B, C such that 1 ≤ A ≤ B < C ≤ N means that you are swapping the block (block = consecutive subsequence) of elements occupying positions A...B with the block of elements occupying positions B+1..C. Of course, the order of elements in a particular block does not change.

This means that you can pick any two adjacent blocks (each of an arbitrary length) and swap them. The problem can easily be solved in N-1 operations, but to make it more difficult, you must think of a faster way.

Input

A natural number 1 < N < 100.

Output

Output at most 50 operations, one per line. Each operation is represented by three numbers as described above.

Example

Input:
5

Output:
2 3 5
1 2 4
2 3 5

Explanation of the sample

(5 4 3 2 1) → (5 2 1 4 3) → (1 4 5 2 3) → (1 2 3 4 5)


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

hide comments
2014-08-07 11:08:44 meiji
It looks that way. Thanks.
2014-08-07 11:08:44 Adrian Satja Kurdija
No, the answer is not unique. I think your solution uses more than 50 operations.

Last edit: 2011-04-28 20:10:31
2014-08-07 11:08:44 meiji
WA...
should it be the unique answer?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.