И снова ханойские башни
Всем наверное известна головоломка "Ханойские башни". В головоломке имеются три стержня и N дисков различного радиуса. Изначально все диски расположены на первом стержне, упорядоченные по радиусу - диск с наибольшим радиусом расположен внизу, а с наименьшим вверху. За один ход разрешается взять верхний диск с любого стержня и переложить его на другой, следуя единственному правилу: нельзя класть больший диск на меньший. В задаче необходимо переложить все диски на последний стержень, совершив наименьшее количество перекладываний.
Легенда гласит, что где-то в Тибете есть монастырь, в котором монахи неустанно передвигают диски со стержня на стержень, решая задачу для 64 дисков. Легенда говорит, что когда работа будет закончена, то настанет конец света.
Поскольку известно, что для решения задачи достаточно совершить 2^N-1 перекладываний, небольшие вычисления показывают, что мир еще некоторое время побудет в безопасности.
Однако недавние открытия археологов показали, что дела могут оказаться намного хуже. В манускрипте, найденном в Тибете, утверждается, что монахи решали задачу не на 3-х, но на M стержнях. Это действительно оказалось проблемой, так как с увеличением числа стержней количество перекладываний согласно описанным правилам резко уменьшается.
Найдите количество перекладываний, которое необходимо совершить для перекладывания N дисков с первого стержня на последний, если в задаче присутствуют M стержней, а также укажите порядок перекладывания дисков.
Входные данные
Входные данные содержат два числа N и M (1 ≤ N ≤ 64, 4 ≤ M ≤ 65).
Выходные данные
В первой строке выведите количество перекладываний L для решения задачи. Следующие L строк должны содержать сами перекладывания. Каждая строка имеет вид
move from to
если диск перекладывается на пустой стержень или
move from to atop
если диск кладется сверху на другой диск.
Радиусы дисков изменяются от 1 до N, стержни пронумерованы от 1 до M.