F. Ханойские башни

Головоломка «Ханойские башни» состоит из трёх стержней с номерами 1, 2, 3. На стержень 1 надета пирамидка из $n$ дисков разного диаметра, снизу самый большой. Диски перекладывают по одному, и больший диск нельзя класть на меньший.

Переложите пирамидку со стержня 1 на стержень 3 за наименьшее число перекладываний и выведите их.

Каждое перекладывание выводится тремя числами: номер диска, номер стержня, откуда его сняли, и номер стержня, куда надели. Диски пронумерованы от 1 до $n$ по возрастанию диаметра.

Кратчайшее решение ровно одно, так что ответ определён однозначно.

Одна строка содержит число $n$ ($1 \le n \le 16$).

Ровно $2^n - 1$ строк с перекладываниями.