Задача №3051. Ремонт в Ханое

Весь теоретический материал - на сайте sdo41.ru в курсе "Профильная школа по информатике".

Постановлением ЮНЕСКО оригинал Ханойской башни был подвергнут реставрации. В связи с этим во время пользования головоломкой нельзя было перекладывать кольца с первого стержня сразу на третий и наоборот.

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

Каждое перемещение задается тремя числами: номер кольца, исходный стержень, конечный стержень.

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

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

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

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

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