{"raw_statement":[{"iden":"statement","content":"Не только на Земле снимают и смотрят реалити-шоу. На планете Нямка тоже есть своё реалити-шоу. Его суть состоит в том, что участника шоу ставят на поле размером NxM в клетку с координатами (0, 0) (координаты отсчитываются от левого верхнего угла поля) и говорят ему идти вправо. Затем участник просто странствует по полю, тратя на каждое перемещение в соседнюю клетку одну секунду, и зрители телешоу ставят ставки на то, где окажется участник через Т секунд. Всё было бы очевидно, если бы поле было пустым, но это не так. На поле присутствуют: \n\nАвтор задач является большим поклонником данного реалити-шоу, поэтому он попросил Вас узнать: в какой точке будет находится через Т секунд участник сегодняшнего выпуска шоу?\n\nВ первой строке через пробел даны два натуральных числа N и M (2 ≤ N, M ≤ 103) – размеры поля. \n\nСледующие N строк содержат по М символов каждая. Символы “u”, “d”, “l”, “r” – обозначают указатели направления. Символ “o” – обозначает пустую клетку. Символ “s” – обозначает суши-бар. Все символы являются строчными буквами английского алфавита.\n\nДалее указаны два целых неотрицательных числа Т и Q через пробел (0 ≤ T, Q ≤ 106). За ними следуют Q строк – описания катапульт. i-я строка содержит пять чисел: x1, y1, x2, y2 и t, где (x1, y1) – координаты появления i-ой катапульты, (x2, y2) – координаты клетки, в которую она стреляет, t – секунда от начала шоу, во время которой катапульта работает (0 ≤ x1, x2 < N, 0 ≤ y1, y2 < M, 0 ≤ t ≤ 106). Гарантируется, что ни одна катапульта не стоит в клетке с суши-баром. \n\nВыведите два целых числа через пробел – координаты клетки, в которой окажется участник через Т секунд.\n\n"},{"iden":"входные данные","content":"В первой строке через пробел даны два натуральных числа N и M (2 ≤ N, M ≤ 103) – размеры поля. Следующие N строк содержат по М символов каждая. Символы “u”, “d”, “l”, “r” – обозначают указатели направления. Символ “o” – обозначает пустую клетку. Символ “s” – обозначает суши-бар. Все символы являются строчными буквами английского алфавита.Далее указаны два целых неотрицательных числа Т и Q через пробел (0 ≤ T, Q ≤ 106). За ними следуют Q строк – описания катапульт. i-я строка содержит пять чисел: x1, y1, x2, y2 и t, где (x1, y1) – координаты появления i-ой катапульты, (x2, y2) – координаты клетки, в которую она стреляет, t – секунда от начала шоу, во время которой катапульта работает (0 ≤ x1, x2 < N, 0 ≤ y1, y2 < M, 0 ≤ t ≤ 106). Гарантируется, что ни одна катапульта не стоит в клетке с суши-баром. "},{"iden":"выходные данные","content":"Выведите два целых числа через пробел – координаты клетки, в которой окажется участник через Т секунд."},{"iden":"примеры","content":"Входные данные3 3oroooooso4 11 1 2 2 2Выходные данные2 1Входные данные3 3dolosorou6 31 0 2 0 12 1 2 2 31 2 0 2 5Выходные данные0 2Входные данные3 3oooosoooo2 0Выходные данные1 1"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N, M \\in \\mathbb{Z}^+ $ be the dimensions of the grid.  \nLet $ G \\in \\{ \\texttt{u}, \\texttt{d}, \\texttt{l}, \\texttt{r}, \\texttt{o}, \\texttt{s} \\}^{N \\times M} $ be the grid, where each cell contains a direction symbol or special marker.  \nLet $ T, Q \\in \\mathbb{Z}_{\\geq 0} $ be the total time and number of catapults.  \nLet $ C = \\{ (x_{1,i}, y_{1,i}, x_{2,i}, y_{2,i}, t_i) \\mid i \\in \\{1, \\dots, Q\\} \\} $ be the set of catapults, where each catapult activates at time $ t_i $ and teleports the participant from $ (x_{1,i}, y_{1,i}) $ to $ (x_{2,i}, y_{2,i}) $.\n\n**Constraints**  \n1. $ 2 \\leq N, M \\leq 10^3 $  \n2. $ 0 \\leq T, Q \\leq 10^6 $  \n3. For each catapult $ i $:  \n   - $ 0 \\leq x_{1,i}, x_{2,i} < N $  \n   - $ 0 \\leq y_{1,i}, y_{2,i} < M $  \n   - $ 0 \\leq t_i \\leq 10^6 $  \n4. No catapult is located on a cell marked `s` (sushi bar).  \n5. The participant starts at $ (0, 0) $ at time $ 0 $, and initially moves right (i.e., direction `r`).  \n6. At each second, the participant moves one cell in the direction indicated by the current cell’s symbol, unless a catapult activates at that second, in which case they are teleported immediately.  \n7. The participant cannot move outside the grid boundaries (grid is bounded).  \n8. The symbol `s` (sushi bar) is irrelevant to movement — it is just a marker; movement follows direction symbols `u`, `d`, `l`, `r`, or default `r` if cell is `o`.\n\n**Objective**  \nCompute the participant’s position $ (x_T, y_T) \\in \\{0, \\dots, N-1\\} \\times \\{0, \\dots, M-1\\} $ after exactly $ T $ seconds, given:  \n- Initial position: $ (x_0, y_0) = (0, 0) $  \n- Initial direction: `r`  \n- For each time step $ \\tau \\in \\{1, \\dots, T\\} $:  \n  - If a catapult activates at time $ \\tau $ and the participant is at its trigger cell $ (x_{1,i}, y_{1,i}) $, teleport to $ (x_{2,i}, y_{2,i}) $.  \n  - Otherwise, move one step in the direction specified by $ G[x][y] $, where $ (x, y) $ is the current cell.  \n  - If the direction leads outside the grid, the participant remains in place.  \n- Output: $ (x_T, y_T) $","simple_statement":"A participant starts at (0, 0) on an N×M grid, moving right. Each second, they follow the direction arrow in the current cell (u, d, l, r) or go straight if it's 'o'. A 's' is a sushi bar — but the participant never stops there. Some catapults activate at time t, instantly moving the participant from (x1, y1) to (x2, y2). After T seconds, where is the participant?","has_page_source":false}