산책

시간 제한2초메모리 제한128 MB

요약

격자에 적힌 방향 글자를 N번의 산책 동안 갱신하며, N번째 산책이 끝나는 교차점을 구한다.

난이도: 보통10점 중 5점
유형: 시뮬레이션, 동적 계획법, 누적 합
정답자: 아직 제출이 없습니다

문제

상근이는 건강을 위해 매일 산책을 한다.

상근이가 사는 마을에는 가로 방향 도로 $(H+1)$ 개와 세로 방향 도로 $(W+1)$ 개가 바둑판처럼 배치되어 있다. 두 도로가 만나는 지점을 교차로라고 하자. 위에서 $a$ 번째, 왼쪽에서 $b$ 번째에 있는 교차로를 $(a, b)$ 로 나타낸다. 상근이의 집은 가장 왼쪽 위 교차로 $(1, 1)$ 에 있고, 산책은 항상 이곳에서 시작한다.

$(1, 1)$ 부터 $(H, W)$ 까지의 교차로, 즉 $H \times W$ 개의 교차로마다 방향을 나타내는 글자가 하나씩 적혀 있다. '오'는 오른쪽, '아'는 아래쪽을 뜻한다.

한 번의 산책은 다음 규칙을 따른다. 현재 교차로에 적힌 글자가

'오'이면, 그 글자를 '아'로 바꾼 뒤 오른쪽 교차로로 이동한다.
'아'이면, 그 글자를 '오'로 바꾼 뒤 아래쪽 교차로로 이동한다.

이렇게 이동을 반복하다가 가장 오른쪽 세로 도로(열 $W+1$ ) 또는 가장 아래쪽 가로 도로(행 $H+1$ )에 있는 교차로에 도착하면 그 지점에서 산책을 끝낸다. 이 경계 교차로에는 글자가 적혀 있지 않다.

교차로의 글자는 산책이 진행되는 동안 계속 바뀌므로, 산책을 할 때마다 경로가 달라질 수 있다. 상근이는 이 방법으로 산책을 계속 반복할 때, $N$ 번째 산책이 어디에서 끝나는지 궁금하다.

$H$ , $W$ 와 각 교차로에 처음 적혀 있는 글자가 주어질 때, $N$ 번째 산책이 끝나는 교차로를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 $H$ , $W$ , $N$ 이 공백으로 구분되어 주어진다. ( $1 \le H, W \le 1000$ , $1 \le N \le 10^7$ )

둘째 줄부터 $H$ 개의 줄에 걸쳐 각 줄마다 $W$ 개의 정수가 주어진다. $i$ 번째 줄의 $j$ 번째 정수는 교차로 $(i, j)$ 에 처음 적혀 있는 글자를 나타내며, $0$ 은 아래쪽을 뜻하는 '아', $1$ 은 오른쪽을 뜻하는 '오'이다.

출력

$N$ 번째 산책이 끝나는 교차로를 $(i, j)$ 라고 할 때, $i$ 와 $j$ 를 공백으로 구분하여 한 줄에 출력한다.

예제7

예제 1
입력
```
3 4 3
1 0 1 1
0 1 0 0
1 0 1 0
```
예상 출력
```
1 5
```
예제 2
입력
```
1 1 1
1
```
예상 출력
```
1 2
```
예제 3
입력
```
1 1 2
1
```
예상 출력
```
2 1
```
예제 4
입력
```
2 2 1
1 1
1 1
```
예상 출력
```
1 3
```
예제 5
입력
```
3 3 5
0 0 0
0 0 0
0 0 0
```
예상 출력
```
3 4
```
예제 6
입력
```
1 5 4
1 0 1 1 0
```
예상 출력
```
2 1
```
예제 7
입력
```
5 1 7
0
1
0
1
0
```
예상 출력
```
3 2
```