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 opearations 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 output: (5 4 3 2 1) --> (5 2 1 4 3) --> (1 4 5 2 3) --> (1 2 3 4 5)