시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 57 28 21 56.757%

문제

상근이는 건강을 위해 산책을 하려고 한다.

상근이가 사는 마을은 아래 그림과 같이 가로 방향 도로가 (H+1)개, 세로 방향 도로가 (W+!)개가 바둑판 모양으로 배치되어 있다. 상근이네 집은 가장 왼쪽 위 교차로에 있으며, 이곳에서 산책을 시작한다.

(a,b)는 위쪽에서 a번째, 왼쪽에서 b번째에 있는 교차로이다. 예를 들어, 상근이네 집은 교차로 (1,1)에 있다.

상근이는 산책 경로가 매일 달라야 질리지 않고 산책을 할 수 있다고 생각한다. 따라서, (1,1)에서 (H,W)까지 H × W개 교차로에 오른쪽을 뜻하는 오 또는 아래를 뜻하는 아를 쓰고, 다음과 같은 규칙에 따라서 산책을 하기로 했다.

교차로에 써있는 문자가 오라면, 이 문자를 지우고 아를 쓴다. 그 다음에 오른쪽으로 진행한다. 만약, 교차로에 써있는 문자가 아라면, 이 문자를 지우고 오를 쓴뒤, 아래로 진행한다.

이렇게 산책을 하다가 가장 오른쪽이나 아래쪽 도로에 도착하면 산책을 종료한다.

상근이는 이런 방법으로 산책을 계속 한다면, N번째 산책 경로가 어떻게 될지 궁금해졌다. H, W와 각 교차로에 써놓은 글자가 주어졌을 때, N번째 산책 경로를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 H, W, N이 주어진다. (1 ≤ H,W ≤ 1000, 1 ≤ N ≤ 107)

둘째 줄부터 H개 줄에는 W개 정수가 주어진다. 이 정수는 상근이가 교차로에 써 놓은 문자의 정보이다. 0은 아래쪽을 의미하는 '아', 1은 오른쪽을 의미하는 '오'이다.

출력

N번째 산책에서 산책을 종료하는 교차로가 (i,j)라고 할 때, i와 j를 공백으로 구분하여 출력한다.

예제 입력

3 4 3
1 0 1 1
0 1 0 0
1 0 1 0

예제 출력

1 5

힌트

출처

Olympiad > 일본정보올림피아드 > JOI 2009 4번