Былинная задача

Нелёгкий выбор вставал перед богатырём Ильёй Муромцем, когда на распутье дорог встречал он камень-указатель: «Налево пойдёшь — коня потеряешь...» и всё в том же духе. Поймал он однажды золотую рыбку и попросил, чтобы впредь никогда ему такие камни не попадались.

И с тех пор ему постоянно встречаются камни с одним-единственным направлением:

• Вверх (Up) 'U',
• Вправо (Right) 'R',
• Вниз (Down) 'D',
• Влево (Left) 'L'.

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

На этот раз Илья Муромец оказался в прямоугольном поле размера N × M, каждая клетка которого содержит камень-указатель. Строки поля нумеруются сверху вниз, столбцы слева направо, нумерация начинается с единицы. Илья Муромец изначально находится в клетке на пересечении строки Y и столбца X. Каждую минуту богатырь перемещается в направлении, указанном на камне в клетке, из которой он уходит.

Ваша задача — выяснить, в какой клетке окажется Илья Муромец через T минут.

Первая строка содержит целые числа N и M (1 ≤ N, M ≤ 20) — соответственно высоту и ширину поля.

Сдедующие N строк описывают поле. Каждая из них содержит M символов 'U', 'R', 'D' или 'L'.

Последняя строка содержит целые числа Y, X и T (1 ≤ Y ≤ N; 1 ≤ X ≤ M; 0 ≤ T ≤ 2 × 10^9) — соответсвенно координаты клетки, в которой изначально находится Илья Муромец, и общее время путешествия в минутах.

Выведите два целых числа Y и X — координаты клетки, в которой окажется Илья Муромец через T минут.

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

Во втором примере на 4 минуте Илья Муромец выходит за левую границу поля.