International OJ

International OJ has $N$ judging servers numbered $1,2,\cdots,N$. Each server has one judging queue and can judge only one submission at a time. Every submission receives AC.

When a submission is inserted into a server's queue, that server judges submissions in FIFO order. If the server is idle, it starts judging the newly inserted submission immediately. While a submission is being judged, the server cannot judge another one. When a submission finishes, its result is reflected in the database at the same time. If another submission is waiting in the queue, the server starts that submission immediately at the same time.

International OJ provides two rankings.

For each problem, completed submissions are ordered by the following rules.

• Smaller judging time comes first.
• If the judging times are equal, earlier completion time comes first.
• If the completion times are also equal, the submission whose type-$1$ query appeared earlier comes first.

Even if one user submits the same problem multiple times, every submission is treated as a separate record.

A user's solved count is the number of distinct problems for which the user has at least one completed AC submission. Multiple submissions to the same problem increase the solved count only once. Users are ordered by the following rules.

• Larger solved count comes first.
• If the solved counts are equal, the user who achieved the current solved count earlier comes first.
• If those times are also equal, lexicographically smaller nickname comes first.

The time at which a user achieved the current solved count is the completion time of the most recent submission that made the user solve a new problem for the first time. A user with no completed submission is not included in the user ranking.

Process $Q$ queries in order. There are three query types.

$1\ t\ i\ x\ y\ s$

At time $t$, insert a submission for problem $x$, with judging time $y$ and nickname $s$, into server $i$'s queue. If server $i$ is idle at time $$, it starts judging the submission immediately.

$2\ t\ x$

Using only submissions completed by time $t$, print the ranking for problem $x$. Print at most the highest-ranked $5$ submissions. For each submission, print its nickname and judging time. If no submission has completed, print -1.

$3\ t$

Using the results reflected in the database by time $t$, print the user ranking. Print at most the highest-ranked $5$ users. For each user, print the nickname and solved count. If no user belongs to the ranking, print -1.

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

For each test case, whenever a type-$2$ or type-$3$ query appears, print its result in query order.

For a type-$2$ query, if records exist, print at most the highest-ranked $5$ records, one per line, in the following format:

$s\ y$

where $$ is the nickname and is the judging time. If there is no record, print on one line.

• $1 \le T \le 200\,000$.
• $1 \le N,Q \le 200\,000$.
• The sum of over all test cases does not exceed .