Юный программист Кеша принял участие в соревнованиях по программированию и вместе со своими друзьями — Лизой, Мишей и Настей — ожидает объявления итогов.
Организаторы приготовили разные шуточные призы для лучших участников и решили выложить их на столе и позволить каждому из участников выбрать приз самостоятельно. Первым будет выбирать приз тот, кто занял первое место, вторым — тот, кто занял второе место и так далее.
Кеша и его друзья увидели среди призов четыре музыкальных инструмента: барабан, бубен, вувузелу и губную гармошку. Оказалось, что у каждого из ребят есть предпочитаемый музыкальный инструмент, который они хотели бы получить в качестве приза. Впрочем, если к моменту, когда подойдет их очередь выбирать приз, именно этого инструмента уже не будет, у каждого из них есть второй предпочитаемый музыкальный инструмент. Если же и второй предпочитаемый инструмент будет отсутствовать, они выберут какой-то другой приз.
Вам известны первый и второй предпочитаемые инструменты для каждого из ребят. Ваша задача — определить, в какой последовательности они должны занять места, чтобы каждый смог взять себе какой-либо из желаемых музыкальных инструментов. Можете считать, что все остальные участники не выберут себе в качестве приза музыкальные инструменты.
Ради упрощения обозначим музыкальные инструменты заглавными латинскими буквами:
В первой строке содержится целое число $$$t$$$ $$$(1 \le t \le 5000)$$$ — количество тестов.
Далее следует $$$t$$$ групп по 4 строки.
В первой строке группы содержатся два символа без пробела, обозначающие первый и второй предпочитаемые инструменты Кеши.
Во второй строке группы содержатся два символа без пробела, обозначающие первый и второй предпочитаемые инструменты Лизы.
В третьей строке группы содержатся два символа без пробела, обозначающие первый и второй предпочитаемые инструменты Миши.
В четвертой строке группы содержатся два символа без пробела, обозначающие первый и второй предпочитаемые инструменты Насти.
Гарантируется, что для каждого из ребят первый и второй предпочитаемые инструменты не совпадают.
Выведите $$$t$$$ строк из четырех символов $$$K$$$ (Кеша), $$$L$$$ (Лиза), $$$M$$$ (Миша), $$$N$$$ (Настя) без пробелов, показывающую последовательность, в которой ребята должны занять места, чтобы каждый имел возможность выбрать один из предпочитаемых музыкальных инструментов.
Если такой последовательности не существует, выведите строку $$$UUUU$$$.
Если для какого-либо теста существует более одного правильного ответа, выводите любой из них.
В первой и второй подзадачах применяется потестовая система оценки. В графе «Баллы» указано количество баллов за тест и в скобках максимальное количество баллов, которое можно набрать за подзадачу. Участнику сообщаются номера тестов подзадачи, которые не были пройдены.
В третьей подзадаче баллы начисляются только в случае прохождения всех тестов этой подзадачи. Участнику сообщается либо номер первого непройденного теста и результат проверки на этом тесте, либо что все тесты подзадачи пройдены.
Для второй и третьей подзадач требуется, чтобы программа верно решала предшествующие подзадачи. Более подробно разбиение на подзадачи показано в таблице ниже.
| Подзадача | Баллы за тест | Ограничения | Необходимые | Информация |
| (баллы | подзадачи | о проверке | ||
| за подзадачу) | ||||
| 1 | 2 (до 10) | $$$t = 1$$$ | нет | полная |
| 2 | 3 (до 30) | $$$2 \le t \le 10$$$ | 1 | полная |
| 3 | 0 (60) | любые допустимые значения t | 1,2 | первая ошибка |
4BCBACDABABBAABCDABBAADADCDACBAAB
NLKM UUUU UUUU NMLK
Поясним приведённый пример.
В нём содержится $$$4$$$ теста.
Первый тест
Ребята хотят получить следующие инструменты:
Если ребята займут места в порядке NLKM, то
Обратите внимание, что ответы LNKM, LKNM и LKMN также являются корректными.
Второй тест
Ребята хотят получить следующие инструменты:
Как можно видеть, Кеша, Лиза и Миша хотят получить только инструменты $$$A$$$ или $$$B$$$. Очевидно, что при любом раскладе один из них не получит желаемый инструмент.
Третий тест
Ребята хотят получить следующие инструменты:
Как можно видеть, на четверых участников приходится $$$3$$$ желаемых инструмента (никто не хочет $$$C$$$). Очевидно, что при любом раскладе один из них не получит желаемый инструмент.
Четвёртый тест
Ребята хотят получить следующие инструменты:
Если ребята займут места в порядке NMLK, то
Обратите внимание, что ответы MNLK, NLMK и NLKM также являются корректными.
| Название |
|---|


