Национальная библиотека Франции — одна из крупнейших библиотек в мире. Но не только уникальное содержание библиотечных фондов привлекает туда туристов. Многие из них посещают библиотеку для того, чтобы воспользоваться бесплатной Wi-Fi сетью.
Здание библиотеки представляет собой поле N × M клеток. Клетки бывают трех типов:
1) препятствие — обозначается символом '#';
2) коридор — обозначается символом '.';
3) комната — обозначается номером от 1-го до 5-ти, в зависимости от назначения (номера могут повторяться).
Посетители могут проходить между соседними по четырем сторонам клетками, но не могут пройти в клетку с препятствием.
Покрытие сети Wi-Fi в библиотеке достаточно слабое, поэтому в комнатах и коридорах помещения часто можно увидеть посетителей с гаджетами, которые ходят по зданию библиотеки в поисках места с хорошим приёмом сигнала.
Однажды турист с друзьями пришёл в библиотеку, чтобы воспользоваться бесплатным Интернетом и после продолжительных поисков обнаружил место с хорошим приёмом Wi-Fi. В силу плохого знания французского языка точно определить своё местоположение в здании библиотеки турист не смог. Тем не менее он решил рассказать своим друзьям об этом месте и отправился на их поиски. Чтобы впоследствии легко вернуться обратно, он решил записать, сколько клеток и в каком направлении он прошёл. Также он решил записывать последовательность A номеров комнат, в которые приходил, но к этой задаче отнесся не очень внимательно и, возможно, пропустил номера некоторых пройденных комнат. Пока турист разыскивал друзей, наступило время закрытия библиотеки, и он был вынужден отправиться домой.
На следующий день турист вновь пришёл в библиотеку. Получив на входе схему библиотеки, он решил по вчерашним заметкам найти клетку, с которой он вчера отправился на поиски друзей.
Искомая клетка должна удовлетворять следующим критериям:
1. Если начать движение из клетки и перемещаться строго в соответствии с записями, то ни в какой момент времени не окажешься за пределами библиотеки или в клетке с препятствием.
2. Если при движении в соответствии с записями выписать последовательность B номеров посещаемых комнат, то записанная ранее туристом последовательность A будет являться подпоследовательностью B.
Вам необходимо определить, сколько клеток в библиотеке подходят туристу. Учтите, что турист мог ошибиться в записях, и в этом случае искомой клетки не существует.
В первой строке задаются размеры билиотеки N и M (1 ≤ N, M ≤ 1000).
Далее следует описание поля в виде N строк по M символов в каждой. Допустимые символы: '#', '.', '1', '2', '3', '4', '5'. Строки задаются от верхней к нижней. Символы в строках от левого к правому.
Далее следует число K перемещений туриста (1 ≤ K ≤ 100).
В следующих K строках задаются перемещения туриста в виде пар Ci Pi, где Ci — символ, обозначающий направление движения (L — движение справа налево, R — движение слева направо, U — движение снизу вверх, D — движение сверху вниз), а Pi (1 ≤ Pi ≤ 999) — число клеток, пройденных в заданном направлении.
В последней строке без пробелов задаётся последовательность номеров комнат A (1 ≤ |A| ≤ 100, 1 ≤ Ai ≤ 5), выписанных туристом при поиске друзей.
Количество клеток, из которых турист мог отправиться на поиски друзей.
4 5
22.#.
1211#
..#.1
.#122
2
L 2
U 1
121
1
4 5
..3#.
213.#
.#33#
1214.
3
L 1
R 2
U 1
1213
3
Комментарий к Примеру 1: подходит клетка [2 3] (строка столбец).
Комментарий к Примеру 2: подходят клетки [2 2], [4 2], [4 3].
