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