Не только на Земле снимают и смотрят реалити-шоу. На планете Нямка тоже есть своё реалити-шоу. Его суть состоит в том, что участника шоу ставят на поле размером NxM в клетку с координатами (0, 0) (координаты отсчитываются от левого верхнего угла поля) и говорят ему идти вправо. Затем участник просто странствует по полю, тратя на каждое перемещение в соседнюю клетку одну секунду, и зрители телешоу ставят ставки на то, где окажется участник через Т секунд. Всё было бы очевидно, если бы поле было пустым, но это не так. На поле присутствуют:
Автор задач является большим поклонником данного реалити-шоу, поэтому он попросил Вас узнать: в какой точке будет находится через Т секунд участник сегодняшнего выпуска шоу?
В первой строке через пробел даны два натуральных числа 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). Гарантируется, что ни одна катапульта не стоит в клетке с суши-баром.
Выведите два целых числа через пробел – координаты клетки, в которой окажется участник через Т секунд.
## Входные Данные
В первой строке через пробел даны два натуральных числа 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). Гарантируется, что ни одна катапульта не стоит в клетке с суши-баром.
## Выходные Данные
Выведите два целых числа через пробел – координаты клетки, в которой окажется участник через Т секунд.
## Примеры
Входные данные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
[samples]
**Definitions**
Let $ N, M \in \mathbb{Z}^+ $ be the dimensions of the grid.
Let $ 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.
Let $ T, Q \in \mathbb{Z}_{\geq 0} $ be the total time and number of catapults.
Let $ 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}) $.
**Constraints**
1. $ 2 \leq N, M \leq 10^3 $
2. $ 0 \leq T, Q \leq 10^6 $
3. For each catapult $ i $:
- $ 0 \leq x_{1,i}, x_{2,i} < N $
- $ 0 \leq y_{1,i}, y_{2,i} < M $
- $ 0 \leq t_i \leq 10^6 $
4. No catapult is located on a cell marked `s` (sushi bar).
5. The participant starts at $ (0, 0) $ at time $ 0 $, and initially moves right (i.e., direction `r`).
6. 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.
7. The participant cannot move outside the grid boundaries (grid is bounded).
8. 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`.
**Objective**
Compute the participant’s position $ (x_T, y_T) \in \{0, \dots, N-1\} \times \{0, \dots, M-1\} $ after exactly $ T $ seconds, given:
- Initial position: $ (x_0, y_0) = (0, 0) $
- Initial direction: `r`
- For each time step $ \tau \in \{1, \dots, T\} $:
- 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}) $.
- Otherwise, move one step in the direction specified by $ G[x][y] $, where $ (x, y) $ is the current cell.
- If the direction leads outside the grid, the participant remains in place.
- Output: $ (x_T, y_T) $