Петя поступил на ФИИТ УрФУ и всё ещё не запомнил, как ориентироваться в учебном корпусе — матмехе. После второй пары Петя бесцельно слоняется по коридорам, которые представляют из себя сплошной лабиринт. Корпус имеет форму прямоугольника ширины $$$W$$$ и высоты $$$H$$$, разделённого на клетки $$$1 \times 1$$$. Клетки бывают четырёх типов:
Как назло уборщицы регулярно начинают мыть пол, поэтому если Петя начнёт двигаться в одном направлении, то он не остановится, пока не упрётся в препятствие. Препятствиями являются граница корпуса, стена, а также запертая дверь, если у Пети нет ключа.
По пути Петя может собирать ключи. Проходя мимо ключа, Петя моментально подбирает его, не останавливаясь. Он может носить с собой неограниченное количество ключей. Любой ключ подходит к любой двери. Если Петя упирается в запертую дверь, он моментально открывает её ключом и продолжает движение без остановки. Ключ остается в замочной скважине двери. Если же у Пети нет с собой ни одного ключа, то запертые двери для него не отличаются от стен.
Также известно, что во время пар декан открывает все двери. Поэтому во время пар на матмехе нет ни одной запертой двери и ни одного ключа. Во время перемены можно найти ключи и/или запертые двери.
Помогите Пете не заблудиться и выбраться в столовую. Он знает, в какой клетке он начал свой путь, а также всю историю своих передвижений. Он сделал $$$L$$$ шагов, каждый из шагов — перемещение в одном из четырех направлений: вверх, вправо, вниз или влево. Для каждого из шагов выведите, сколько клеток лабиринта он проскользил в этом направлении.
В первой строке даны три целых числа $$$H$$$, $$$W$$$ и $$$D$$$ — высота корпуса, ширина корпуса, а также число $$$D$$$, обозначающее время; если $$$D = 0$$$, то дело происходит во время пары, иначе — на перемене ($$$1 \le H, W \le 10^5$$$, $$$H \cdot W \le 10^5$$$, $$$0 \le D \le 1$$$).
Далее идут $$$H$$$ строк, описывающих корпус матмеха. Каждая строка состоит из $$$W$$$ символов, не разделённых пробелами. Всего есть $$$5$$$ возможных символов. Символ «.» (код $$$46$$$) обозначает пустую клетку. Символ «#» (код $$$35$$$) обозначает стену. Символ «K» обозначает клетку с ключом. Символ «L» обозначает клетку с запертой дверью. Символ «S» обозначает клетку, где начинает Петя — эта клетка считается пустой. Гарантируется, что есть ровно один символ «S».
Гарантируется, что если $$$D = 0$$$, то символы «K» и «L» в описании корпуса отсутствуют. Если $$$D = 1$$$, то есть хотя бы один символ «K» или «L».
В следующей строке дано целое число $$$L$$$ — количество шагов, сделанных Петей ($$$1 \le L \le 10^5$$$).
В последней строке даны $$$L$$$ символов, не разделённых пробелами. Всего есть $$$4$$$ возможных символа, которые могут встречаться: «U», «R», «D», «L». Они обозначают направления вверх, вправо, вниз и влево соответственно. Корпус ориентирован так, как дан во вводе: первая строка является самой верхней, первый столбец является самым левым.
Выведите $$$L$$$ строк, в каждой строке выведите одно целое число. В $$$i$$$-й строке выведите количество клеток, которые Петя прошёл, сделав $$$i$$$-й шаг.
$$$$$$ \begin{array} {|c|c|c|c|}
\hline \textbf{Подзадача} & \textbf{Баллы} & \textbf{Ограничения} & \textbf{Необх. подзадачи} \\ \hline 1 & 25 & H \cdot W \le 100, L \le 100, D = 0 & \\ \hline 2 & 25 & H \cdot W \le 100, L \le 100, D \le 1 & 1 \\ \hline 3 & 25 & H \cdot W \le 10^5, L \le 10^5, D = 0 & 1 \\ \hline 4 & 25 & H \cdot W \le 10^5, L \le 10^5, D \le 1 & 1, 2, 3 \\ \hline \end{array} $$$$$$
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены, а также решение корректно работает на примерах из условия.
3 4 0 S..# .... #... 6 RDRULD
2 2 1 1 3 0
1 6 1 LKSKLL 4 RRLR
2 0 4 4
