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
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.
