Time limit 2000/2000/2000/2000 ms. Memory limit 65000/65000/65000/65000 Kb.
Нелёгкий выбор вставал перед богатырём Ильёй Муромцем, когда на распутье дорог встречал он камень-указатель: «Налево пойдёшь — коня потеряешь...» и всё в том же духе. Поймал он однажды золотую рыбку и попросил, чтобы впредь никогда ему такие камни не попадались.
И с тех пор ему постоянно встречаются камни с одним-единственным направлением:
- Вверх (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.
Примеры
Входные данные | Выходные данные |
3 3 RDR DLU RRU 1 1 7 | 2 3 |
3 3 RDR LLU RRU 1 1 7 | -1 |
Примечание
Во втором примере на 4 минуте Илья Муромец выходит за левую границу поля.
Для отправки решений необходимо выполнить вход.
|