Рабочее место участника

Головоломку "Ханойская башня" придумал французский математик Эдуард Люка. Игрушка, продававшаяся в 1883 году, состояла из 8 колец. Задача состоит в том, чтобы перенести за наименьшее число ходов пирамиду из колец разного диаметра с одного колышка на другой, используя третий колышек как вспомогательный. За один раз разрешается переносить только одно кольцо, причем нельзя класть кольцо большего диаметра на кольцо меньшего диаметра. В описании к игре рассказывалось о мифической "Пирамиде браминов", состоявшей из 64 золотых колец, в храме индийского города Бенареса. Каждый ход жрецы сопровождают молитвами, помогающими им действовать в правильном направлении. По преданию, как только жрецы храма сделают последний ход, грянет гром, храм рассыплется в пыль, погаснут звезды и наступит конец света. Так как для завершения работы жрецам потребуется `10^14` лет, то можно считать это предсказание верным: не только храм за такое время превратится в пыль, но и по расчетам физиков все звезды превратятся в холодные тела или черные дыры.

Решается головоломка достаточно просто. Например, чтобы переместить пирамиду из 8 дисков с колышка #1 на #2, используя #3, нужно

Наименьшее количество ходов для решения головоломки из `N` дисков равно `2^N-1`.

Напишите программу, которая по количеству дисков и числу сделанных ходов в минимальной последовательности ходов, требующихся для решения головоломки, определяет размещение дисков по колышкам после указанного хода. Диски пронумерованы от 1 (самый маленький) до `N` (самый большой). Требуется перенести диски с колышка #1 на колышек #2.

Во входном файле содержится две строки. В первой строке содержится целое число `N` – число дисков (`1\ ≤\ N\ ≤\ 100`). Во второй строке содержится целое число `K` – число выполненных ходов (`0\ ≤\ K\ ≤\ 2^N-1`).

В выходной файл вывести три строки – в `j`-й строке содержится количество и номера дисков, начиная с меньшего диска, на `j`-ом колышке, разделенные пробелом.

8
19

3 6 7 8
2 3 4
3 1 2 5