Seat Reservation

Daejeon Science High School has a first-come, first-served system for reserving study seats.

There are $X$ students. Each student has a unique student number from $1$ to $X$. Each student can apply for one of $C$ seats. Each seat has a unique number from $1$ to $C$.

The system works as follows.

• Each seat is either reserved or unreserved. Before any student applies, every seat is unreserved.
• If a student applies for a seat that is already reserved, the application is invalid. An application that is not invalid is successful.
• A student whose application succeeds is assigned that seat immediately, and the seat becomes reserved.
• If a student who already has a seat succeeds in applying for another seat, the seat they had before becomes unreserved.

The system failed, so the applications were not processed correctly. Fortunately, the server kept a log of the applications. Each log entry has the time $T$ of the application, the seat number $S$ the student applied for, and the student number $N$. A smaller $T$ means the application happened earlier.

Given the number of students and the log, write a program that finds the seat each student is finally assigned.

The first line contains the number of students $X$, the number of seats $C$, and the number of log entries $K$, separated by spaces. $(1 \le X, C, K \le 100\,000)$

Each of the next $K$ lines contains an application time $T$, the seat number $S$, and the student number $N$, separated by spaces. $(0 \le T \le 1\,000\,000\,000$, $1 \le S \le C$, $1 \le N \le X)$

All application times $T$ are distinct. The log is not necessarily sorted by time.

On each line, print the student number and the seat number that student is finally assigned, in increasing order of student number, separated by a space. Do not print students who did not apply for any seat or who never succeeded in applying for a seat.