D. Робот в подвале
ограничение по времени на тест
4 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

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

Подвал в доме профессора представляет собой прямоугольник n × m, разбитый на квадратные клетки 1 × 1. Некоторые клетки — стены, которые непроходимы, остальные клетки проходимы. Из любой проходимой клетки можно попасть в любую другую проходимую клетку, двигаясь через смежные по ребрам проходимые клетки. Одна из проходимых клеток является выходом из подвала. Робот находится ровно в одной из проходимых клеток, в том числе, он может находиться в клетке выхода.

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

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

На выполнение каждой команды тратится электроэнергия, а профессор не хочет получить в конце месяца большой счет за электричество. Поэтому он хочет найти наименьший префикс в выписанной им последовательности, который гарантированно приведет робота к выходу после его выполнения. Именно с этой просьбой профессор тревожит вас в столь поздний час.

Входные данные

В первой строке находятся три целых числа n, m и k (3 ≤ n, m ≤ 150, 1 ≤ k ≤ 105). В последующих n строках содержится по m символов — описание подвала профессора: «#» означает стену, «.» — проходимую клетку, а «E» — выход из подвала (эта клетка тоже проходима). Гарантируется, что до выхода можно добраться из любой проходимой клетки, а все клетки по периметру прямоугольника n × m — стены. Ровно одна клетка является выходом из подвала. В последней строке находится k символов — описание последовательности команд, что профессор выписал на листочек. «L», «R», «U», «D» означают команды влево, вправо, вверх и вниз соответственно.

Выходные данные

В выходной файл выведите длину наименьшего префикса, который гарантированно приводит робота к клетке выхода. Другими словами, робот должен оказаться в клетке выхода после выполнения всех команд из префикса (в процессе выполнения команд робот мог приходить в клетку выхода, а затем уходить из нее, но нас интересует положение робота только в самом конце), где бы он ни находился в подвале изначально. Если профессор ошибся и никакой префикс (включая всю последовательность) не приводит робота к выходу, выведите «-1» (без кавычек). Если единственная проходимая клетка поля — выход, то выведите «0» (без кавычек).

Примеры
Входные данные
5 5 7
#####
#...#
#...#
#E..#
#####
UULLDDR
Выходные данные
6
Входные данные
5 5 7
#####
#.#.#
#...#
#E..#
#####
UULLDDR
Выходные данные
-1
Входные данные
5 3 2
###
#.#
#.#
#E#
###
DD
Выходные данные
2