시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
3.0 초 512 MB 4156 1123 (27%) 1016
문제
삼성이는 매일 출근을 한다. 도로는 아래 그림과 같이 가로 방향 도로가 $(H+1)$개, 세로 방향 도로가 $(W+1)$개가 바둑판 모양으로 배치되어 있다. 삼성이네 집은 $(1,1)$이고, 회사는 $(H+1, W+1)$에 있다. $(a, b)$는 위쪽에서 $a$번째, 왼쪽에서 $b$번째에 있는 교차로이다. ![image](/download_file/0a134c0d712a5f9cc4c891664404111b1db41662558293290546cde83c805469/image6.png/?show=true "교차로 사진") 매일 같은 경로로 운전해간다면 졸음운전의 위험이 굉장히 높아진다. 따라서 아래와 같은 재미있는 방법으로 회사까지 가려고 한다. * 항상 오른쪽, 또는 아래쪽으로 이동한다. * 맨 아래와, 맨 오른쪽을 제외한 각 교차로에 ‘아’ 혹은 ‘오’가 적혀있다. * ‘아’라고 적힌곳에 있다면, 아래로 가야한다. 또 ‘오’라고 적힌곳에 있다면 오른쪽으로 가야한다. * 지나친 교차로의 ‘아’와 ‘오’는 다음날 서로 바뀐다. ‘아’를 지났다면, 다음날 그 교차로는 ‘오’로 바뀌어져 있다. $N$번째 날의 출근 경로를 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 $H, W, N$이 주어진다. $(1 \le H, W \le 1,000, 1 \le N \le 10,000,000)$ 두 번째 줄부터 $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 ``` #### 힌트 ![image](/download_file/88af6f254e29e143af81a831f13c35f010dcc2adae9feb42fedaf7fed43e15d0/image7.png/?show=true "힌트")