항공권의 연속 좌석 배정

문제

한 항공편의 좌석은 R개의 행으로 이루어져 있고, 각 행에는 왼쪽부터 번호가 붙은 C개의 좌석이 있다. 행 번호는 앞쪽부터 1번에서 R번까지이고, 각 행의 좌석 번호는 1번에서 C번까지이다. 항공권 발권기는 일행이 같은 행의 연속한 좌석에 앉도록 요청을 처리한다. 처음에는 모든 좌석이 비어 있으며, 발권기가 확인하는 현재 행은 1번 행이다. 각 요청에는 일행의 인원 K가 적혀 있다. 발권기는 먼저 현재 행에서 아직 배정하지 않은 좌석 수를 확인한다. 현재 행에 K명 이상이 앉을 수 있으면, 그 행의 남은 좌석 중 가장 왼쪽 좌석부터 K개를 배정한다. 이때 배정된 좌석은 다시 사용할 수 없으며 현재 행은 그대로 유지한다. 현재 행의 남은 좌석이 K개보다 적고 다음 행이 존재하면, 현재 행의 남은 좌석을 모두 사용하지 않기로 확정하고 바로 다음 행으로 이동한다. 그런 다음 새 행의 1번 좌석부터 K개를 배정한다. 모든 요청의 인원은 한 행의 좌석 수 이하이므로 새 행에서는 반드시 배정할 수 있다. 이전 행에서 포기한 좌석으로 돌아가거나 서로 다른 행에 일행을 나누어 앉히는 일은 없다. 현재 행의 남은 좌석이 부족하고 다음 행도 없으면 해당 요청은 실패한다. 실패한 요청은 좌석 배정 상태를 전혀 바꾸지 않는다. 따라서 마지막 행에 좌석이 조금 남아 있을 때 큰 일행의 요청이 실패하더라도, 뒤에 도착한 작은 일행은 그 좌석을 배정받을 수 있다. 한 행의 좌석을 모두 배정한 직후에도 현재 행은 유지하며, 다음 요청을 처리할 때 위 규칙에 따라 이동 여부를 판단한다. 요청을 입력 순서대로 처리하고 각 요청의 배정 결과를 구하라. 성공한 요청에는 배정한 행과 첫 좌석의 번호를 기록한다.

입력

첫째 줄에 행 수 R, 한 행의 좌석 수 C, 요청 수 N이 주어진다. 1 ≤ R ≤ 100,000, 1 ≤ C ≤ 99, 1 ≤ N ≤ 25,000이다.
다음 N개 줄에 각 요청의 인원 K가 하나씩 주어진다. 1 ≤ K ≤ C이다.
입력의 모든 수는 정수이다.

출력

각 요청에 대해 입력 순서대로 한 줄씩 출력한다. 배정에 성공하면 행 번호와 배정한 첫 좌석 번호를 공백으로 구분하여 출력한다. 배정할 수 없으면 0 0을 출력한다.

2 5 5
3
4
2
1
1

1 1
2 1
0 0
2 5
0 0

1 4 3
4
1
4

1 1
0 0
0 0

출처: Devin.KR 자체 제작