Задача №3052. Циклические башни

На дорогах Ханоя было введено одностороннее круговое движение, поэтому теперь диск со стержня 1 можно перекладывать только на стержень 2, со стержня 2 на 3, а со стержня 3 на 1.

Решите головоломку с учетом этих ограничений. Вам не нужно находить минимальное решение, но количество совершенных перемещений не должно быть больше 200000, при условии, что количество дисков не превосходит 10.
Каждая строка вывода содержит номер перемещаемого кольца, номер стержня "откуда" и номер стрежня "куда". Кольца нумеруются от самого маленького до самого большого.

Входные данные

Вводится натуральное число n.

Выходные данные

Выведите ответ на задачу.

Примеры
Входные данные
2
Выходные данные
1 1 2
1 2 3
2 1 2
1 3 1
2 2 3
1 1 2
1 2 3
Сдать: для сдачи задач необходимо войти в систему