eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Ханойські вежі

Ханойські вежі

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Кожному програмісту відома ломиголовка "Ханойські вежі". Коротко нагадаємо її умову.

Є 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 комбінацій, відсортованих у порядку їх слідування у грі.

Приклад

Вхідні дані #1
3 4
ACB
BCA
ABB
BAA
Вихідні дані #1
BAA
BCA
ACB
ABB
Джерело 2013-2014 ACM Central Region of Russia Quarterfinal, Rybinsk 2013/10/17