Stroll

Time limit2sMemory limit128 MB

Summary

Simulate the letters on a grid as N successive walks from the top-left, and report the endpoint of the N-th walk.

Level: Medium5 of 10
Topics: Simulation, Dynamic programming, Prefix sum
Solved: No attempts yet

Problem

Sanggeun goes for a stroll every day to stay healthy.

His town is laid out like a go board, with $(H+1)$ horizontal roads and $(W+1)$ vertical roads. Call each point where two roads meet an intersection. The intersection in the $a$ -th row from the top and the $b$ -th column from the left is written $(a, b)$ . Sanggeun's house sits at the top-left intersection $(1, 1)$ , and every stroll starts there.

Each of the $H \times W$ intersections from $(1, 1)$ to $(H, W)$ has a single direction letter written on it: R means right and D means down.

One stroll proceeds by the following rule. If the letter on the current intersection is

R, change it to D and move to the intersection to the right;
D, change it to R and move to the intersection below.

He repeats this until he reaches an intersection on the rightmost vertical road (column $W+1$ ) or the bottommost horizontal road (row $H+1$ ), where the stroll ends. These boundary intersections have no letter.

Because the letters change as he walks, each stroll can follow a different route. Sanggeun wonders where his $N$ -th stroll will end if he keeps repeating this process.

Given $H$ , $W$ , and the letter initially written on each intersection, write a program that finds the intersection where the $N$ -th stroll ends.

Input

The first line contains three integers $H$ , $W$ , and $N$ , separated by spaces. ( $1 \le H, W \le 1000$ , $1 \le N \le 10^7$ )

Each of the next $H$ lines contains $W$ integers. The $j$ -th integer on the $i$ -th line describes the letter initially written on intersection $(i, j)$ : $0$ is D (down) and $1$ is R (right).

Output

Let $(i, j)$ be the intersection where the $N$ -th stroll ends. Print $i$ and $j$ on one line, separated by a space.

Examples7

Example 1
Input
```
3 4 3
1 0 1 1
0 1 0 0
1 0 1 0
```
Expected output
```
1 5
```
Example 2
Input
```
1 1 1
1
```
Expected output
```
1 2
```
Example 3
Input
```
1 1 2
1
```
Expected output
```
2 1
```
Example 4
Input
```
2 2 1
1 1
1 1
```
Expected output
```
1 3
```
Example 5
Input
```
3 3 5
0 0 0
0 0 0
0 0 0
```
Expected output
```
3 4
```
Example 6
Input
```
1 5 4
1 0 1 1 0
```
Expected output
```
2 1
```
Example 7
Input
```
5 1 7
0
1
0
1
0
```
Expected output
```
3 2
```