자리 신청

대전과학고등학교에는 선착순으로 자습 좌석을 신청하는 시스템이 있다.

학생은 총 $X$명이며, 학번은 $1$ 이상 $X$ 이하의 서로 다른 정수이다. 각 학생은 $C$개의 좌석 중 하나를 골라 신청할 수 있다. 좌석에는 $1$ 이상 $C$ 이하의 서로 다른 번호가 붙어 있다.

시스템은 다음과 같이 동작한다.

• 각 좌석은 신청된 좌석 또는 신청되지 않은 좌석 중 하나의 상태를 가진다. 학생이 신청하기 전에는 모든 좌석이 신청되지 않은 좌석이다.
• 학생이 신청한 좌석이 이미 신청된 좌석이면 그 신청은 무효가 된다. 무효가 되지 않은 신청은 성공한 신청이다.
• 신청에 성공한 학생은 곧바로 그 좌석을 배정받고, 해당 좌석은 신청된 좌석이 된다.
• 이미 좌석을 배정받은 학생이 다른 좌석 신청에 성공하면, 이전에 배정받았던 좌석은 신청되지 않은 좌석으로 돌아간다.

시스템이 고장 나서 신청이 제대로 처리되지 않았다. 다행히 서버에 신청 로그가 남아 있다. 각 로그는 신청 시각 $T$, 신청한 좌석 번호 $S$, 학생의 학번 $N$으로 이루어진다. $T$가 작을수록 먼저 일어난 신청이다.

학생 수와 로그가 주어질 때, 각 학생이 최종적으로 배정받은 좌석 번호를 구하는 프로그램을 작성하시오.

첫 번째 줄에 학생 수 $X$, 좌석의 개수 $C$, 로그의 개수 $K$가 공백으로 구분되어 주어진다. $(1 \le X, C, K \le 100\,000)$

다음 $K$개의 줄에는 신청 시각 $T$, 신청한 좌석 번호 $S$, 학생의 학번 $N$이 공백으로 구분되어 주어진다. $(0 \le T \le 1\,000\,000\,000$, $1 \le S \le C$, $1 \le N \le X)$

모든 로그의 신청 시각 $T$는 서로 다르다. 로그는 시각 순으로 정렬되어 있지 않을 수도 있다.

각 줄에 학번의 오름차순으로 학생의 학번과 배정받은 좌석 번호를 공백으로 구분하여 출력한다. 좌석을 신청하지 않았거나, 좌석 신청에 한 번도 성공하지 못한 학생은 출력하지 않는다.