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