HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Unsorted > problem:


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

Section problems

• Большее число
• Большее число
• Бонни и Клайд
• Босс
• 1
• Будильник
• Бутерброд
• Бутерброд
• Былинная задача
• Варианты заданий
• Введение (подсказки к задачам)
• Вверх ногами
• Великая китайская разборка
• Високосный год
• Владимир и бассейн
• Всё и сразу
• Всё как у людей

Feedback

If you notice incorrect translations in Contester, please let author know.

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 минуте Илья Муромец выходит за левую границу поля.

 

Для отправки решений необходимо выполнить вход.

www.contester.ru