Постановою ЮНЕСКО оригінал Ханойської вежі було піддано реставрації. У зв'язку з цим під час користування головоломкою не можна було перекладавати кільця з першого стержня відразу на третій і навпаки. Напишіть рекурсивну процедуру, яка виводить послідовність перекладувань з врахуванням таких обмежень. \InputFile Одне натуральне число \textbf{n} (\textbf{1} ≤ \textbf{n }≤ \textbf{7}) - кількість кілець на першому стержні. \OutputFile Вивести послідовність ходів для перекладування усіх кілець на третій стержень у такому порядку: номер кільця, з якого стержня, на який стержень. Кільця нумеруються від самого маленького до самого великого. Кількість ходів не повинна перевищувати \textbf{10^5}.