Робот-коллекционер наклеек
Один из любимых видов спорта в RoboLand — это Ралли Роботов. Соревнование проходит на огромной прямоугольной арене, состоящей из квадратных ячеек размером N на M. Некоторые ячейки пустые, в некоторых находятся наклейки для Альбома Чемпионата Мира по Футболу (они очень ценятся искусственными интеллектами в RoboLand), а другие заняты столбами, поддерживающими крышу арены. Во время ралли роботы могут перемещаться по любой ячейке арены, кроме тех, где стоят столбы, так как они блокируют движение. Путь робота определяется последовательностью инструкций. Каждая инструкция обозначается одним из символов: 'D', 'E' и 'F', что означает, соответственно, "повернуть на 90 градусов вправо", "повернуть на 90 градусов влево" и "двигаться вперед на одну ячейку". Роботы начинают ралли с определенной стартовой позиции и строго следуют данной последовательности инструкций (в конце концов, они роботы!). Каждый раз, когда робот попадает в ячейку с наклейкой, он собирает её. Наклейки не восстанавливаются, то есть каждая может быть собрана только один раз. Если робот пытается переместиться в ячейку со столбом, он останавливается и остается в той же ячейке, сохраняя направление. То же самое происходит, если робот пытается покинуть арену.
Вам дано описание арены, указывающее расположение столбов и наклеек, и последовательность инструкций для робота. Ваша задача — написать программу, которая определит количество собранных роботом наклеек.
Входные данные
Вход содержит несколько тестов. Первая строка каждого теста содержит три целых числа N, M и S (1 ≤ N, M ≤ 100, 1 ≤ S ≤ 5×10^4), разделенных пробелами, которые обозначают количество рядков, количество столбцов арены и количество инструкций для робота соответственно. Следующие N строк описывают рядки ячеек арены и содержат строку из M символов. Первая строка описания арены — это самая северная, а первый столбец в строке — самый западный.
Каждая ячейка в арене описывается одним из следующих символов:
'.' - обычная ячейка;
'*' - ячейка с наклейкой;
'#' - ячейка со столбом;
'N', 'S', 'L', 'O' - ячейка, где робот начинает ралли (единственная на арене). Буква обозначает начальную ориентацию робота (Север, Юг, Восток и Запад соответственно).
Последняя строка ввода содержит последовательность из S символов 'D', 'E' и 'F', представляющих инструкции для робота.
Последний тестовый случай сопровождается строкой, содержащей только три нуля, разделенные пробелом.
Выходные данные
Для каждого ралли, описанного во входных данных, ваша программа должна вывести одну строку с одним целым числом, указывающим количество наклеек, собранных роботом во время ралли.