로봇

이미지 출처: flickr.com

Gunnar는 여가 시간에 바닥의 화살표를 따라 움직이는 작은 로봇을 프로그래밍했다. 그의 바닥은 칸들로 나뉘어 있으며, 그는 각 칸에 그 칸을 둘러싼 네 칸 중 하나를 가리키는 화살표를 놓았다.

Gunnar는 로봇을 바닥의 한 칸에 놓는다. 로봇은 자신이 있는 칸의 화살표를 확인하고, 화살표가 가리키는 칸으로 이동한다. 그곳에서 로봇은 같은 과정을 반복한다. 그 칸의 화살표를 확인하고, 그 화살표를 따라 이동하며, 이 과정을 계속한다.

Gunnar는 로봇이 의도한 대로 작동하는지 완전히 확신하지 못하지만, 직장에 가야 하므로 하루 종일 로봇을 지켜볼 시간이 없다. Gunnar는 여러분에게 도움을 요청한다. 로봇이 시작하는 칸과 로봇이 이동해야 하는 걸음 수가 주어질 때, 로봇이 어느 칸에서 끝나야 하는지 Gunnar가 알아낼 수 있도록 도와줄 수 있는가?

배점

그룹 | 점수 | 제한

1 | 15 | $n=1$, $q=1$, $k \leq 1\,000$, $q\leq 100$이고 문자는 <`'와 >`'만 가능하다

2 | 15 | $n=1$ , $q\leq 100$이고 문자는 <`'와 >`'만 가능하다

3 | 15 | $q\leq 100$이고 문자는 <`', >', ``v'만 가능하다

4 | 15 | $k \leq 1\,000$, $q\leq 100$

5 | 15 | $q\leq 10$

6 | 25 | 추가 제한 없음

입력의 첫째 줄에는 바닥의 행 수와 열 수를 나타내는 두 정수 $n$와 $m$ ($1 \leq n,m \leq 500$)가 주어진다.

이어서 각각 $m$개의 문자로 이루어진 $n$개의 줄이 주어지며, 이 줄들이 함께 Gunnar의 바닥을 나타낸다. 문자는 ^`' (위를 가리키는 화살표), <' (왼쪽을 가리키는 화살표), ``v' (아래를 가리키는 화살표) 또는 ``>`' (오른쪽을 가리키는 화살표) 중 하나이다.

그다음 한 줄에 질의의 수를 나타내는 정수 $q$ ($1 \leq q \leq 10^4$)가 주어진다. 이어서 각 질의마다 한 줄씩 $q$개의 줄이 주어지며, 각 줄에는 세 정수 $x$, $y$, $k$ ($1\leq x \leq n$, $1 \leq y \leq m$ 및 $1 \leq k \leq 10^9$)가 주어진다. 여기서 $x$는 로봇이 시작하는 칸의 행을 나타내고, $y$는 로봇이 시작하는 칸의 열을 나타내며, $k$는 로봇이 이동해야 하는 걸음 수를 나타낸다.

각 질의마다 두 정수 $x'$와 $y'$를 한 줄에 출력한다. 여기서 $x'$는 로봇이 마지막에 위치하는 칸의 행이고, $y'$는 로봇이 마지막에 위치하는 칸의 열이다.

로봇이 바닥 밖으로 걸어 나가는 경우는 절대로 주어지지 않는다.