Informatica Online Judge

  산책 [0373 / 0175]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 15   Total Tried : 21


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[]

Background

GSHS마을에 사는 정모군은 어느 날 건강을 위하여 산책을 방과후에 하기로 결심했다. 정모군이 사는 GSHS마을에는 아래 그림과 같이 동서 방향으로 H+1개의 도로가 있고, 남북방향으로 W+1개의 도로가 바둑판 형태로 만들어져 있다. 정군의 집은 가장 북서쪽 교차점에 위차하고, 여기서부터 산책을 시작한다.
이후에 북쪽에서 a번째, 서쪽으로부터 b번째의 교차점을 (a,b)로 표현한다고 할 때, 정군의 집은 (1,1)이 된다.


그림 : GSHS마을의 지도 (H=3, W=4인 경우) 지도의 위쪽이 북쪽 왼쪽이 서쪽이다.

정군은 산책 경로가 매일 달라지는 것이 재미있을 것이라고 생각하므로, (1,1)로부터 (H,W)까지 H*W개의 교차점에 “동” 또는 “남”의 문자를 적고 다음 규칙에 따라서 매일 산책을 하기로 했다.

- 문자가 적힌 교차점에 있을 경우, 그 교차점에 적힌 문자가 “동”이라면 “남”으로, “남”이라면 “동”으로 고치고 원래 적혀 있던 문자의 방향의 다음 교차점 까지 진행한다.
- 가장 동쪽이나 남쪽의 도로에 도착하면 산책이 종료된다.

이 계획을 세운후 정군은 앞으로 산책에서 자기가 어떤 경로로 가게 될지 알고 싶어졌다. 정군을 위해서 정군이 N번째 산책을 할 때의 경로를 예상하는 프로그램을 작성하시오.

Input

첫 번째 줄에는 3개의 정수가 공백으로 구분되어 젹혀있다. 이 정수는 H, W, N을 의미한다. H, W, N은 각각 1 <= H <= 1000, 1 <= W <= 1000, 1 <= N <= 10,000,000을 만족한다.
둘째 줄부터 H+1번째 줄에는 각각 W개의 정수가 공백으로 구분되어 입력된다. 이 들은 정군이 최초에 교차점에 적힌 문자의 정보를 표시한다. i+1행의 j번째 정수가 0이라면 교차점(i,j)에 적힌 문자가 “남”이라는 의미이고, 1이라면 교차점(i,j)에 적힌 문자가 “동”이라는 의미를 나타낸다.

Output

N번째 산책에 대해서 정군이 산책의 도착점의 좌표가(i,j)일 경우, i, j를 공백으로 구분하여 출력하라.

IO Example

입력
3 4 3
1 0 1 1
0 1 0 0
1 0 1 0

출력
1 5

설명)


Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]