C. Музыкальный выбор
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Юный программист Кеша принял участие в соревнованиях по программированию и вместе со своими друзьями — Лизой, Мишей и Настей — ожидает объявления итогов.

Организаторы приготовили разные шуточные призы для лучших участников и решили выложить их на столе и позволить каждому из участников выбрать приз самостоятельно. Первым будет выбирать приз тот, кто занял первое место, вторым — тот, кто занял второе место и так далее.

Кеша и его друзья увидели среди призов четыре музыкальных инструмента: барабан, бубен, вувузелу и губную гармошку. Оказалось, что у каждого из ребят есть предпочитаемый музыкальный инструмент, который они хотели бы получить в качестве приза. Впрочем, если к моменту, когда подойдет их очередь выбирать приз, именно этого инструмента уже не будет, у каждого из них есть второй предпочитаемый музыкальный инструмент. Если же и второй предпочитаемый инструмент будет отсутствовать, они выберут какой-то другой приз.

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

Входные данные

Ради упрощения обозначим музыкальные инструменты заглавными латинскими буквами:

  • $$$A$$$ — барабан,
  • $$$B$$$ — бубен,
  • $$$C$$$ — вувузела,
  • $$$D$$$ — губная гармошка.

В первой строке содержится целое число $$$t$$$ $$$(1 \le t \le 5000)$$$ — количество тестов.

Далее следует $$$t$$$ групп по 4 строки.

В первой строке группы содержатся два символа без пробела, обозначающие первый и второй предпочитаемые инструменты Кеши.

Во второй строке группы содержатся два символа без пробела, обозначающие первый и второй предпочитаемые инструменты Лизы.

В третьей строке группы содержатся два символа без пробела, обозначающие первый и второй предпочитаемые инструменты Миши.

В четвертой строке группы содержатся два символа без пробела, обозначающие первый и второй предпочитаемые инструменты Насти.

Гарантируется, что для каждого из ребят первый и второй предпочитаемые инструменты не совпадают.

Выходные данные

Выведите $$$t$$$ строк из четырех символов $$$K$$$ (Кеша), $$$L$$$ (Лиза), $$$M$$$ (Миша), $$$N$$$ (Настя) без пробелов, показывающую последовательность, в которой ребята должны занять места, чтобы каждый имел возможность выбрать один из предпочитаемых музыкальных инструментов.

Если такой последовательности не существует, выведите строку $$$UUUU$$$.

Если для какого-либо теста существует более одного правильного ответа, выводите любой из них.

Система оценки

В первой и второй подзадачах применяется потестовая система оценки. В графе «Баллы» указано количество баллов за тест и в скобках максимальное количество баллов, которое можно набрать за подзадачу. Участнику сообщаются номера тестов подзадачи, которые не были пройдены.

В третьей подзадаче баллы начисляются только в случае прохождения всех тестов этой подзадачи. Участнику сообщается либо номер первого непройденного теста и результат проверки на этом тесте, либо что все тесты подзадачи пройдены.

Для второй и третьей подзадач требуется, чтобы программа верно решала предшествующие подзадачи. Более подробно разбиение на подзадачи показано в таблице ниже.

ПодзадачаБаллы за тестОграниченияНеобходимыеИнформация
(баллыподзадачио проверке
за подзадачу)
12 (до 10)$$$t = 1$$$нетполная
23 (до 30)$$$2 \le t \le 10$$$1полная
30 (60)любые допустимые значения t1,2первая ошибка

Пример
Входные данные
4
BC
BA
CD
AB
AB
BA
AB
CD
AB
BA
AD
AD
CD
AC
BA
AB
Выходные данные
NLKM
UUUU
UUUU
NMLK
Примечание

Поясним приведённый пример.

В нём содержится $$$4$$$ теста.

Первый тест

Ребята хотят получить следующие инструменты:

  • Кеша хочет получить $$$B$$$, в случае отсутствия $$$B$$$ хочет получить $$$C$$$;
  • Лиза хочет получить $$$B$$$, в случае отсутствия $$$B$$$ хочет получить $$$A$$$;
  • Миша хочет получить $$$C$$$, в случае отсутствия $$$C$$$ хочет получить $$$D$$$;
  • Настя хочет получить $$$A$$$, в случае отсутствия $$$A$$$ хочет получить $$$B$$$.

Если ребята займут места в порядке NLKM, то

  • Настя выберет $$$A$$$;
  • Лиза выберет $$$B$$$;
  • Кеша не сможет выбрать $$$B$$$, поэтому выберет $$$C$$$;
  • Миша не сможет выбрать $$$C$$$, поэтому выберет $$$D$$$.

Обратите внимание, что ответы LNKM, LKNM и LKMN также являются корректными.

Второй тест

Ребята хотят получить следующие инструменты:

  • Кеша хочет получить $$$A$$$, в случае отсутствия $$$A$$$ хочет получить $$$B$$$;
  • Лиза хочет получить $$$B$$$, в случае отсутствия $$$B$$$ хочет получить $$$A$$$;
  • Миша хочет получить $$$A$$$, в случае отсутствия $$$A$$$ хочет получить $$$B$$$;
  • Настя хочет получить $$$C$$$, в случае отсутствия $$$C$$$ хочет получить $$$D$$$.

Как можно видеть, Кеша, Лиза и Миша хотят получить только инструменты $$$A$$$ или $$$B$$$. Очевидно, что при любом раскладе один из них не получит желаемый инструмент.

Третий тест

Ребята хотят получить следующие инструменты:

  • Кеша хочет получить $$$A$$$, в случае отсутствия $$$A$$$ хочет получить $$$B$$$;
  • Лиза хочет получить $$$B$$$, в случае отсутствия $$$B$$$ хочет получить $$$A$$$;
  • Миша хочет получить $$$A$$$, в случае отсутствия $$$A$$$ хочет получить $$$D$$$;
  • Настя хочет получить $$$A$$$, в случае отсутствия $$$A$$$ хочет получить $$$D$$$.

Как можно видеть, на четверых участников приходится $$$3$$$ желаемых инструмента (никто не хочет $$$C$$$). Очевидно, что при любом раскладе один из них не получит желаемый инструмент.

Четвёртый тест

Ребята хотят получить следующие инструменты:

  • Кеша хочет получить $$$C$$$, в случае отсутствия $$$C$$$ хочет получить $$$D$$$;
  • Лиза хочет получить $$$A$$$, в случае отсутствия $$$A$$$ хочет получить$$$C$$$;
  • Миша хочет получить $$$B$$$, в случае отсутствия $$$B$$$ хочет получить $$$A$$$;
  • Настя хочет получить $$$A$$$, в случае отсутствия $$$A$$$ хочет получить $$$B$$$.

Если ребята займут места в порядке NMLK, то

  • Настя выберет $$$A$$$;
  • Миша выберет $$$B$$$;
  • Лиза не сможет выбрать $$$A$$$, поэтому выберет $$$C$$$;
  • Кеша не сможет выбрать $$$C$$$, поэтому выберет $$$D$$$.

Обратите внимание, что ответы MNLK, NLMK и NLKM также являются корректными.