Ремонт в Ханої

Постановою ЮНЕСКО оригінал Ханойської вежі було піддано реставрації. У зв'язку з цим під час користування головоломкою не можна було перекладавати кільця з першого стержня відразу на третій і навпаки. Напишіть рекурсивну процедуру, яка виводить послідовність перекладувань з врахуванням таких обмежень.

Вхідні дані

Одне натуральне число n (1 ≤ n ≤ 7) - кількість кілець на першому стержні.

Вихідні дані

Вивести послідовність ходів для перекладування усіх кілець на третій стержень у такому порядку: номер кільця, з якого стержня, на який стержень. Кільця нумеруються від самого маленького до самого великого. Кількість ходів не повинна перевищувати 10^5.

Приклади