Lara Croft과 New Game

올해 출시되는 Lara Croft 시리즈의 차기 게임에 대해 들어 보았을 수도 있다. 또한 그 예고편을 보았을 수도 있다. 하지만 줄거리의 핵심은 분명 놓쳤을 것이므로, 비밀의 장막을 걷어 주겠다.

Lara는 또 하나의 위험한 던전을 탐험하려 한다. 게임 디자이너들은 익숙하고 오래된 2D 환경을 사용하기로 했다. 던전은 n개의 행과 m개의 열로 이루어진 직사각형 행렬로 나타낼 수 있다. 칸 (x, y)은 x-th행의 y-th열에 있는 칸이다. Lara는 변을 맞댄 이웃한 칸 사이를 네 방향 모두로 이동할 수 있다.

게다가 그녀는 모든 함정을 피하기 위해 이동 경로까지 미리 정했다. 그녀는 행렬의 왼쪽 위 모서리인 칸 (1, 1)에서 던전에 들어간다. 그런 다음 왼쪽 아래 모서리인 칸 (n, 1)까지 계속 아래로 내려간다. 그다음 뱀처럼 이동하기 시작한다. 오른쪽 끝까지 이동하고, 한 칸 위로 이동한 뒤, 2-nd열의 칸까지 왼쪽으로 이동하고, 다시 한 칸 위로 이동한다. 방문하지 않은 칸이 더 이상 없을 때까지 이동한다. 주어진 n와 m는 그녀가 항상 칸 (1, 2)에서 이동을 마치도록 정해져 있다.

Lara는 이미 이웃한 칸으로 k번 이동했다. 현재 위치를 구할 수 있는가?

유일한 줄에 세 정수 n, m, k (2 ≤ n, m ≤ 109, n is always even, 0 ≤ k < n·m)가 주어진다. k는 32-bit 정수형에 들어가지 않는다는 점에 유의한다!

Lara가 k번 이동한 후 도착하는 칸을 출력한다. 칸이 위치한 행과 열을 출력하면 된다.

다음은 4행 3열 행렬에서 그녀가 이동하는 경로이다: