402435: GYM100771 H Реалити-шоу

H. Реалити-шоуограничение по времени на тест2 секундыограничение по памяти на тест64 мегабайтавводстандартный вводвыводстандартный вывод

Не только на Земле снимают и смотрят реалити-шоу. На планете Нямка тоже есть своё реалити-шоу. Его суть состоит в том, что участника шоу ставят на поле размером NxM в клетку с координатами (0, 0) (координаты отсчитываются от левого верхнего угла поля) и говорят ему идти вправо. Затем участник просто странствует по полю, тратя на каждое перемещение в соседнюю клетку одну секунду, и зрители телешоу ставят ставки на то, где окажется участник через Т секунд. Всё было бы очевидно, если бы поле было пустым, но это не так. На поле присутствуют:

1. Указатели направления. Они представлены в виде букв английского алфавита: “u” – указывает, что участник должен двигаться вверх, “d” – указывает, что участник должен двигаться вниз, “l” – указывает, что участник должен двигаться влево, “r” – указывает, что участник должен двигаться вправо. Если участник приходит в точку с указателем направления, то далее он следует в том направлении, куда указывает указатель направления, даже если он не сделал ни одного шага.
2. Катапульты. Катапульты работают одну секунду, если участник в этот момент оказывается в клетке с катапультой, то он перелетает в клетку, в которую стреляет катапульта. Перелёт участника из клетки с катапультой в новую занимает одну секунду. За один день реалити-шоу появляется Q катапульт. Если в клетке с катапультой есть указатель направления, то участник будет идти в заданном им направлении после переброски, если в новой клетке нет иного указателя направления. Гарантируется, что никакие две катапульты, находящиеся в одной клетке, не работают одновременно.
3. Суши-бар. Если участник в какой-то момент времени окажется на линии или в столбце, которые содержат суши-бар, то он почувствует запах роллов и направится в сторону суши-бара, игнорируя указатели, но не катапульты. Он будет двигаться по линии или по столбцу в сторону суши-бара. Затраты на перемещение в соседнюю клетку так же составят одну секунду. Если участник дойдёт до суши-бара, то он проведёт там всё время до конца реалити-шоу, поедая разнообразные роллы, мисо-супы, суши и вкуснейшую лапшу. Гарантируется, что на всём поле суши-бар всегда один.
4. Поле имеет границы. Если участник попробует пройти влево от клетки с координатами (а, 0), то он попадёт в точку с координатами (N-1-a, M-1). Если участник попробует пройти вверх от клетки с координатами (0, а), то он попадёт в точку с координатами (N-1, M-1-a), аналогично с другими границами.

Автор задач является большим поклонником данного реалити-шоу, поэтому он попросил Вас узнать: в какой точке будет находится через Т секунд участник сегодняшнего выпуска шоу?

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

В первой строке через пробел даны два натуральных числа N и M (2 ≤ N, M ≤ 10³) – размеры поля.

Следующие N строк содержат по М символов каждая. Символы “u”, “d”, “l”, “r” – обозначают указатели направления. Символ “o” – обозначает пустую клетку. Символ “s” – обозначает суши-бар. Все символы являются строчными буквами английского алфавита.

Далее указаны два целых неотрицательных числа Т и Q через пробел (0 ≤ T, Q ≤ 10⁶). За ними следуют Q строк – описания катапульт. i-я строка содержит пять чисел: x1, y1, x2, y2 и t, где (x1, y1) – координаты появления i-ой катапульты, (x2, y2) – координаты клетки, в которую она стреляет, t – секунда от начала шоу, во время которой катапульта работает (0 ≤ x1, x2 < N, 0 ≤ y1, y2 < M, 0 ≤ t ≤ 10⁶). Гарантируется, что ни одна катапульта не стоит в клетке с суши-баром.

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

Выведите два целых числа через пробел – координаты клетки, в которой окажется участник через Т секунд.

ПримерыВходные данные

3 3
oro
ooo
oso
4 1
1 1 2 2 2

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

2 1

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

3 3
dol
oso
rou
6 3
1 0 2 0 1
2 1 2 2 3
1 2 0 2 5

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

0 2

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

3 3
ooo
oso
ooo
2 0

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

1 1