Problem D
Þjarki

Image from flickr.com

In his spare time Gunnar has programmed a small robot that follows arrows on the floor. His floor is divided into squares and he has put an arrow down on each square that points to one of its four adjacent squares.

Gunnar puts the robot down on a square on the ground. The robot looks at the arrow on the square its on and moves to the square the arrow is pointing to. The robot then repeats this, looks at the arrow on the cell it has moved to, follows it, and so on.

Gunnar isn’t quite sure whether the robot works as it should and doesn’t have the time to look after it, he has to go to work after all. Gunnar asks for your assistance. Given the square the robot starts on and how many steps the robot will take, can you help Gunnar determine what square the robot ends up on?

Input

The first line of the input contains two integers $n$ and $m$ ($1 \leq n,m \leq 500$), the number of rows and number of columns making up the cells of the floor.

Then there are $n$ lines, each with $m$ letters, which together denote Gunnars’ floor. The letters can be ‘^’ (arrow pointing up) ‘<’ (arrow pointing left), ‘v’ (arrow pointing down) or ‘>’ (arrow pointing right).

Then there will be a line with the integer $q$ ($1 \leq q \leq 10^4$), the number of queries. Then follow $q$ lines, one for each query, each containing three integers $x$, $y$ and $k$ ($1\leq x \leq n$, $1 \leq y \leq m$ and $1 \leq k \leq 10^9$), where $x$ denotes the row of the square the robot starts, $y$ denotes the column of the square the robot starts on and $k$ denotes the number of steps the robot will take.

Output

For each query, print a single line with two integers $x’$ and $y’$ where $x’$ is the row of the square the robot ends on and $y’$ is the column of the square the robot ends on.

The robot will never move past the edge of the floor.

Scoring

3 4
>vv<
>>>v
^<^<
3
1 1 5
3 1 7
1 4 2

3 4
2 3
2 3

1 5
><<<<
2
1 5 3
1 2 2

1 2
1 2