Дано клеточное поле из N строк и M столбцов. На поле есть запрещенные для движения клетки. Вы начинаете «гонку» из клетки в левом верхнем углу, а заканчиваете ее в правом нижнем. У вас есть соперник, стартовая точка и путь движения которого известны заранее (путь необязательно оптимальный). Вам предлагается за минимальное число шагов достичь финиша по следующим правилам:

• Двигаться можно только в соседнюю по горизонтали или вертикали свободную клетку (одно перемещение – это переход на соседнюю клетку).

• Передвижение осуществляется поочередно: сначала ходит соперник, затем вы.

• Не допускаются нахождение обоих участников в одном квадрате одновременно.

• Ходы соперников обязательны.

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

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

Формат входных данных

В первой строке размер поля: два числа через пробел 0 < N, М ≤ 150. Далее идет N строк в каждой из которых по M символов, описывающих поле: точка (.) – клетка свободна, решетка (#) – непроходимая клетка. В следующей строке два числа – номер строки и столбца, где находится ваш соперник. Далее следует строка с описанием пути соперника: R – движение вправо, L – влево, U – вверх, D - вниз. Количество ходов соперника не более 32000.

Формат выходных данных

Содержит единственное число – минимальное число шагов, необходимое для достижения финиша, в случае невозможности вывести –1.

3 5
.....
.#...
.#...
1 4
R

6

3 5
.....
.#...
.#...
1 4
LLLRLRRR

12