Consider a Deterministic Finite Automaton(DFA) which takes N states numbered from 0 to N-1, with alphabets 0 and 1. Now consider a string of 0s and 1s, let the decimal value of this string as M. For e.g., if string be "010" then the decimal value or M is 2. The speciality in our DFA is that when we simulate the string through this DFA, it finally takes us to the state with the same number as of M%N, where % is the modulus operator. For e.g. if our string is "1100" i.e. M is 12 and N is 5, then after simulating this string through DFA, it will reach to state 12%5 i.e. state no. 2. Since M%N can be any number from 0 to N-1, and the states in our DFA are also from 0 to N-1, there must always be some state we will reach. Assume the starting state of DFA is 0.

You are given N, the no. of states in our DFA. Print a transition table for this DFA.

Input

An integer N

Output

Output the N lines where i-th line will contain 3 space-separated integers a b c where 

a=(i-1), 

b is the state no. where state no. a takes us to, for input alphabet 0

c is the state no. where state no. a takes us to, for input alphabet 1

i.e. i-th line will show the transition of state no. (i-1)

Constraints

1 ≤ N ≤ 100

SAMPLE INPUT
5

SAMPLE OUTPUT
0 0 1
1 2 3
2 4 0
3 1 2
4 3 4

Explanation

Lets take the above example with string "1100" and N=5,

Initially we are at state no. 0 (given).
After reading '1' of our string, we goes to state no. 1 (1st line of output tells about transition from state no. 0)
After reading the next '1', we goes to state no. 3 (2nd line of output)
After reading '0' of our string, we goes to state no. 1 (4th line of output)
After reading the final input alphabet i.e. '0', we goes to state no. 2. and that is also 12%5.
n=input()
cnt=0
for i in range(0,n):
    print i,
    print (cnt)%n,(cnt+1)%n
    cnt=cnt+2