eolymp
bolt
Try our new interface for solving problems
Problems

Repair in Hanoi

Repair in Hanoi

Time limit 1 second
Memory limit 128 MiB

By UNESCO resolution the original Tower of Hanoi was subjected to restoration. Thereby during solution of the puzzle it is forbidden to move a disk from the first peg directly to the third peg and vice versa. Write a recursive procedure that prints a sequence of moves subject to such restrictions.

Input data

One integer n (1n7) - the number of disks on the first peg.

Output data

Print the sequence of moves for transferring all the rings to the third peg in the next order: number of the disk, starting peg, destination peg. Disks are numbered from the smallest to the largest. The number of moves should not exceed 10^5.

Examples

Input example #1
1
Output example #1
1 1 2
1 2 3