21539번 - Графический редактор <<Хамелеон>> 점수다국어

Юный информатик осваивает новый графический редактор <<Хамелеон>>. Этот редактор обладает необыкновенной простотой. Он поддерживает ровно два цвета --- чёрный и белый, и один инструмент --- <<Хамелеон>>.

Поле редактора --- это квадрат $N \times N$ клеток. На одной из клеток поля находится курсор-хамелеон. Его можно передвигать в пределах поля в четырех направлениях --- вверх, вниз, вправо или влево ровно на одну клетку. Цвет курсора всегда должен совпадать с цветом клетки, в которой он находится. Для этого, когда он перемещается на клетку другого цвета, должно произойти одно из двух событий: либо курсор меняет свой цвет на цвет этой клетки, либо наоборот --- клетка меняет свой цвет на цвет курсора. Например, если курсор перемещается из чёрной клетки в белую, либо он должен перекраситься в белый цвет, либо белая клетка, в которой он теперь находится, должна стать чёрной. Если клетка и курсор имеют одинаковый цвет, то их цвет не изменяется.

Изначально курсор имеет чёрный цвет и находится в левой верхней клетке поля. Эта клетка также окрашена в чёрный цвет. Все остальные клетки поля окрашены в белый цвет.

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

В первой строке входного файла задано число $N$ ($5 \leqslant N \leqslant 100$) --- размер поля.

В следующих $N$ строках описывается картинка, которую необходимо получить. Каждая строка описания картинки имеет длину $N$ и состоит из символов <<W>>, если соответствующая клетка белая, и <<B>>, если чёрная.

Последняя строка файла содержит номер теста.

Выходной файл должен содержать одну строку с описанием искомой последовательности действий.

Для обозначения перемещения влево, вверх, вправо или вниз с изменением цвета курсора следует использовать буквы <<l>>, <<u>>, <<r>> или <<d>> соответственно. Для обозначения перемещения влево, вверх, вправо или вниз с изменением цвета клетки следует использовать буквы <<L>>, <<U>>, <<R>> или <<D>> соответственно. Если курсор перемещается на клетку своего цвета, можно использовать как заглавную, так и строчную букву.

В этой задаче тестовые данные доступны участникам олимпиады. 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20

Тесты нумеруются в соответствии с названиями файлов от $0$ до $20$. Тест из примера имеет номер $0$, он используется для предварительной проверки.Тесты с номерами с $1$ по $20$ включительно используются для окончательной проверки.

Окончательная проверка данной задачи осуществляется на наборе из $20$ тестов. Каждый тест оценивается из $5$ баллов. Тесты оцениваются независимо. 

Тест считается пройденным, если выведенная последовательность содержит не более $5\,000\,000$ действий и приводит к правильному результату. 

Первые $10$ тестов оцениваются в $5$ баллов, если тест пройден.

Оставшиеся $10$ тестов оцениваются следующим образом. Если тест пройден, то:

• в 5 баллов, если ответ содержит не более $3 N^2$ действий;
• в 4 балла, если ответ содержит не более $5 N^2$ действий;
• в 3 балла, если ответ содержит не более $10 N^2$ действий;
• в 2 балла, если ответ содержит не более $2\mbox{,}5 N^3$ действий;
• в 1 балл, если ответ содержит не более $5\,000\,000$ действий.