Областная олимпиада школьников по информатике (личное первенство)

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

Напишите программу, моделирующую кормление сентипода. Сентипод движется со скоростью одна клетка в секунду. Если в начале секунды была сказана команда, то сентипод поворачивает голову в указанном направлении (поворот головы выполняется мгновенно), а затем движется в том направлении, куда направлена его голова. Если не было подано никаких команд, то сентипод продолжает двигаться в том же направлении, что и на предыдущей секунде. Если впереди ограда площадки или его собственное туловище, то сентипод топчется на месте, иначе продвигается на одну клетку. Если на клетке был кабидж, то длина сентипода мгновенно увеличивается на одну единицу (хвост сентипода при этом не сдвигается с места). Голова сентипода расположена на первом сегменте туловища и может повернуться на любой угол кратный 90 градусов.

В первой строке входного файла содержатся два целых числа, разделенных пробелом – размеры площадки `N` (`1\ ≤\ N\ ≤\ 100`) и `M` (`1\ ≤\ M\ ≤\ 100`). Далее следует `N` строк, содержащих по `M` символов – начальное состояние площадки. Символ '.' (точка) означает пустую клетку, символ '@' – клетку с кабиджем. Символ '%' встречается ровно один раз и показывает начальную позицию сентипода, его длина в начале моделирования равна единице, а голова направлена в сторону правой ограды. Последняя строка содержит посекундную запись команд, сказанных учеником. Символ '-' (минус) означает отсутствие команд в начале соответствующей секунды, символ 'L' – команду «налево», а символ 'R' – команду «направо». Количество символов в последней строке не более `100\ 000`.

В выходной файл вывести `N` строк по `M` символов – конечное состояние площадки. Голова сентипода изображается символом '%', а туловище – символом '#'.

3 5
%..@.
.@.@@
..@..
-----LLLRR--L-

....#
.%###
..@..

3 4
....
.%@.
....
-

....
.#%.
....