탐사 드로이드

Hoth 행성에 배치된 뒤로, 이곳에서 내린 결정 중 최악이라는 생각이 들었다. 행성은 춥고 할 일이 없으며, 설상가상으로 제국이 누군가 숨어 있는지 확인하려고 탐사 드로이드를 계속 보낸다. 그래도 탐사 드로이드에는 대응할 수 있다!

기지 근처 들판에는 이 드로이드들이 일정한 간격으로 깔려 있다. 기지에는 들판의 남서쪽(왼쪽 아래) 모서리, 좌표 $(1, 1)$에 터렛이 있다. $n \times m$ 격자점(정수 좌표를 가진 점) 중 $(1, 1)$을 제외한 모든 점에 드로이드가 하나씩 있다.

$3 \times 5$ 격자의 예:

1행은 가장 아래, $n$행은 가장 위, 1열은 왼쪽, $m$열은 오른쪽이다.

기지 좌표는 $(1, 1)$이고, 드로이드는 $(1..n, 1..m)$ 범위의 양의 좌표 중 $(1, 1)$을 뺀 모든 위치에 있다. 기지 터렛은 1행에서 열 번호가 더 큰 쪽, 즉 동쪽을 향한다. 터렛은 다음 방식으로 동작하도록 프로그래밍되어 있다. 시선 안에 드로이드가 있으면 그 드로이드를 파괴한다. 없으면 드로이드가 보일 때까지 반시계 방향으로 회전한다. 모든 드로이드가 파괴될 때까지 이 과정을 계속한다.

이 알고리즘을 실행할 때 $i$번째로 파괴되는 드로이드의 위치를 구하라.

입력은 테스트 케이스 하나로 구성된다. 첫 줄에 세 정수 $n$, $m$($1 \le n, m \le 10^6$, $n$과 $m$이 동시에 1일 수는 없다), $q$($1 \le q \le 100$)가 주어진다. 격자는 $n$행 $m$열이며, 답해야 할 질의는 $q$개다. 이어지는 $q$개 줄에는 각각 정수 $i$($1 \le i < n \times m$) 하나가 주어지며, 이는 $i$번째로 파괴되는 드로이드를 묻는 질의다.

질의 순서대로 $q$개 줄을 출력한다. 각 질의마다 파괴되는 드로이드의 행 $r$과 열 $c$를 공백으로 구분해 출력한다.