Олимпиадный тренинг

Задача . A. Доска с домино

Задача

У Алисы есть клеточная доска из $2$ рядов и $n$ столбцов. Она полностью покрыла доску с помощью $n$ доминошек размера $1 \times 2$ — Алиса могла класть их как вертикально, так и горизонтально, и каждая клетка доски была покрыта ровно одной доминошкой.

Теперь Алиса решила показать одну из строк Бобу. Помогите Бобу и определите, как может выглядеть другая строка доски!

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

Во входных данных находятся несколько наборов входных данных. В первой строке задано одно целое число $t$ ($1 \leq t \leq 5000$) — количество наборов входных данных. Далее следуют сами наборы.

В первой строке каждого набора задано одно целое число $n$ ($1 \leq n \leq 100$) — ширина доски.

Во второй строке каждого набора задана строка $s$, состоящая из $n$ букв, каждая буква — это L, R, U или D, описывающих левую, правую, верхнюю или нижнюю половину доминошки, соответственно (изучите примечания для лучшего понимания). Данная строка описывает одну из строк доски.

Дополнительное ограничение: каждый набор входных данных соответствует хотя бы одному допустимому покрытию доски доминошками.

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

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

Примечание

В первом наборе входных данных Алиса показывает Бобу верхнюю строку. Вся доска может выглядеть следующим образом:

$\text{[math]}$

Во втором наборе Алиса показывает Бобу нижнюю строку. Вся доска может выглядеть следующим образом:

$\text{[math]}$

В третьем наборе Алиса показывает Бобу нижнюю строку. Вся доска может выглядеть следующим образом:

$\text{[math]}$

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

$\text{[math]}$

Примеры

№	Входные данные	Выходные данные
1	4 1 U 2 LR 5 LRDLR 6 UUUUUU	D LR LRULR DDDDDD

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	5

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет