Вы пытаетесь запрограммировать робота для движения по двумерному лабиринту и найти выход.

Лабиринт представлен сеткой с n строками и m столбцами. Некоторые ячейки сетки имеют препятствия, которые робот не может пройти. Другие ячейки пусты, которые робот может свободно пройти. Только одна из пустых ячеек в сетке отмечена как выход, и робот немедленно выйдет из лабиринта, как только достигнет этого места.

Вы можете запрограммировать робота, отправив ему командную строку. Командная строка состоит из символов L, U, R, D, соответствующих направлениям слева, вверх, вправо, вниз, соответственно. Затем робот начнет выполнять команды, переместившись в соседнюю ячейку в направлениях, указанных в командной строке. Если робот столкнулся с препятствием или с краем сетки, он проигнорирует команду, но он продолжит работу с остальными командами. Робот также будет игнорировать все команды после достижения выходной ячейки.

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

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

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

Первая строка содержит два целых числа n и m (1 ≤ n, m ≤ 50).

Каждая из следующих n строк содержит m символов, описывающих сетку. Пустые ячейки обозначаются символом `.', начальное положение робота задается как R, препятствия как #, выход как E.

Следующая и последняя строка содержит командную строку Вашего друга, состоящую от 1 до 50 символов включительно.

Гарантируется, что лабиринт содержит в точности одну R и одну E, причем всегда существует путь от R к E.

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

Выведите одно целое число - минимальное время, необходимое для установки программы.