В компании NAUMEN проводится тестирование новейшего ПО для квадрокоптеров. Вове, работающему в NAUMEN, было поручено запустить квадрокоптер на клетчатом поле. Но вот беда — подул сильный ветер, и квадрокоптер стал неуправляемым! Вове нужно как можно быстрее его поймать.

Клетчатое поле имеет h рядов, пронумерованных от 1 до h, и w столбцов, пронумерованных от 1 до w. Каждая клетка имеет болотистость (целое число от 1 до 999 999) и направление ветра (одно из четырёх: вверх, вниз, влево или вправо).

Вова начинает в клетке в ряду r₁ и столбце c₁ и ходит по полю как хочет. Он может переместиться на клетку, имеющую общую сторону с его текущей клеткой, на это у него уходит количество секунд, равное болотистости клетки, куда он хочет переместиться. Более формально, чтобы переместиться на соседнюю клетку с болотистостью x, Вова ждёт x секунд, после чего моментально переходит на выбранную клетку. Выходить за пределы поля Вова не может. Вова также может решить никуда не ходить, а стоять на текущей клетке в течение произвольного количества времени.

Квадрокоптер начинает в клетке в ряду r₂ и столбце c₂ и перемещается по направлению ветра со скоростью 1 клетка в секунду. Более формально, по прошествии каждой секунды квадрокоптер моментально перелетает на соседнюю клетку в направлении ветра. Направление вверх соответствует уменьшению номера ряда, вниз — увеличению номера ряда, влево — уменьшению номера столбца, вправо — увеличению номера столбца. Если ветер в текущей клетке направлен за пределы поля, то квадрокоптер улетает с поля, после чего его нельзя поймать.

Как только Вова окажется в одной клетке с квадрокоптером, Вова сможет поймать его. При этом если Вова оказывается в клетке в тот же момент, когда квадрокоптер улетает с этой клетки, Вове не удаётся его поймать. Определите, сможет ли Вова поймать квадрокоптер, и если да, то найдите наименьшее возможное количество секунд, за которое он сможет это сделать.

В первой строке через пробел заданы два целых числа h и w — высота и ширина поля (1 ≤ h, w ≤ 250; w · h ≠ 1).

Во второй строке через пробел заданы два целых числа r₁ и c₁ — начальное положение Вовы (1 ≤ r₁ ≤ h; 1 ≤ c₁ ≤ w).

В третьей строке через пробел заданы два целых числа r₂ и c₂ — начальное положение квадрокоптера (1 ≤ r₂ ≤ h; 1 ≤ c₂ ≤ w). Гарантируется, что Вова и квадрокоптер начинают в разных клетках.

Далее идут h строк, задающих болотистость клеток. В i-й из них через пробел заданы w чисел от 1 до 999 999 включительно; j-е из чисел равно болотистости клетки в ряду i в столбце j.

Далее идут h строк, задающих направление ветра в клетках. В i-й из них даны w заглавных букв «U», «D», «L» или «R», не разделённых пробелом; j-й из символов соответствует направлению ветра в ряду i в столбце j. Символ «U» означает направление вверх, «D» — вниз, «L» — влево, «R» — вправо.

Если Вова не сможет поймать квадрокоптер, выведите единственное число −1. Иначе, выведите наименьшее возможное количество секунд, за которое Вова сможет поймать квадрокоптер.