Робот-колекціонер наліпок#6926
Одним з улюблених видів спорту в RoboLand є Роботичне Ралі. Це змагання проводиться у великій прямокутній арені, яка складається з квадратних клітин розміром рядків на стовпців. Деякі клітини порожні, деякі містять наліпки для Альбому Чемпіонату Світу з Футболу (які дуже цінуються штучними інтелектами в RoboLand), а інші зайняті стовпами, що підтримують дах арени. Під час ралі роботи можуть займати будь-яку клітину в арені, за винятком тих, що містять стовпи, оскільки вони блокують рух робота. Шлях робота в арені під час ралі визначається послідовністю інструкцій. Кожна інструкція представлена одним із наступних символів: 'D', 'E' та 'F', що означають, відповідно, "повернути на 90 градусів вправо", "повернути на 90 градусів вліво" та "рухатися вперед на одну клітину". Роботи починають ралі з певної початкової позиції в арені і точно слідують за заданою послідовністю інструкцій (зрештою, вони ж роботи!). Коли робот займає клітину, що містить наліпку Кубка, він збирає її. Наліпки не замінюються, тобто кожна наліпка може бути зібрана лише один раз. Коли робот намагається переміститися в клітину, що містить стовп, він зупиняється, залишаючись у клітині, де був, з тією ж орієнтацією. Те ж саме відбувається, коли робот намагається залишити арену.
Дано карту арени, що описує положення стовпів і наліпок, та послідовність інструкцій для робота, ви повинні написати програму, щоб визначити кількість наліпок, зібраних роботом.
Вхід містить декілька тестових випадків. Перша строка тестового випадку містить три цілі числа , та (1 \le N, M \le 100, 1 \le S \le 5 \times 10^4), розділені пробілами, що вказують відповідно кількість рядків, кількість стовпців арени та кількість інструкцій для робота. Кожен з наступних рядків описує рядок клітин арени і містить рядок з символів. Перший рядок, що з'являється в описі арени, є найбільш північним, перший стовпець, що з'являється в описі рядка клітин арени, є найбільш західним.
Кожна клітина в арені описується одним з наступних символів:
'.' - звичайна клітина;
'*' - клітина, що містить наліпку;
'#' - клітина, що містить стовп;
'N', 'S', 'L', 'O' - клітина, де робот починає ралі (лише одна в арені). Літера представляє початкову орієнтацію робота (Північ, Південь, Схід і Захід, відповідно).
Останній рядок у вхідних даних містить послідовність з символів серед 'D', 'E' та 'F', що представляють інструкції для робота.
Останній тестовий випадок супроводжується рядком, що містить лише три нулі, розділені пробілом.
Для кожного ралі, описаного у вхідних даних, ваша програма повинна вивести один рядок, що містить одне ціле число, яке вказує кількість наліпок, зібраних роботом під час ралі.
Приклад 1