Каждому программисту известна головоломка "Ханойские башни". Кратко напомним ее условие. Имеются \textbf{3} стержня: \textbf{A}, \textbf{B}, \textbf{C}. Изначально \textbf{n} дисков разного диаметра находятся на стержне \textbf{A}: наименьший диск расположен сверху, и далее к низу по возрастанию диаметра. Второй и третий стержни пустые. Необходимо переместить все диски со стержня \textbf{A} на стержень \textbf{B} используя \textbf{C} как дополнительный. За один шаг разрешается снять \textbf{1} верхний диск и положить его либо на пустой стержень, либо на другой стержень на диск с большим диаметром. Почти все книги по программированию содержат рекурсивное решение этой задачи. Далее приведена процедура на языке Паскаль. \textbf{Procedure Hanoi (A, B, C: integer; N:integer);} \textbf{Begin} \textbf{If N>0 then} \textbf{Begin} \textbf{Hanoi (A, C, B, N-1);} \textbf{Writeln(‘Disk ’, N, ‘ from ‘, A, ‘ to ‘, B);} \textbf{Hanoi (C, B, A, N-1)} \textbf{End} \textbf{End;} Например, комбинация "\textbf{BСA}" обозначает, что наименьший диск расположен на стержне \textbf{B}, средний на стержне \textbf{С}, а наибольший на стержне \textbf{A}. Члены жюри, готовясь к соревнованию, иногда играют в эту игру, записывая текущие комбинации (каждую на отдельном листке бумаги). Однако позже все эти листки перемешались. Напишите программу, которая установит, встречалась ли указанная комбинация в игре. \InputFile Первая строка содержит два числа \textbf{n }(\textbf{1 }≤ \textbf{n }≤ \textbf{250}) -- число дисков, и \textbf{m} (\textbf{1 }≤ \textbf{m }≤ \textbf{1000}) - количество комбинаций. Следующие \textbf{m} строк содержат \textbf{m} комбинаций. Каждая комбинация состоит из \textbf{n} заглавных букв ("\textbf{A}", "\textbf{B}" или "\textbf{C}") - расположение \textbf{n} дисков на стержнях. Первая (левая) буква указывает на позицию (имя стержня) наименьшего диска, вторая буква - на позицию второго наибольшего диска и так далее. \OutputFile Вывести \textbf{m} строк -- \textbf{m} комбинаций, отсортированных в порядке их следования в игре.