#480 International OJ

Statement

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 $t$ , 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.

Input

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

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

Each case is given in the following format:

$N\ Q$ $\mathrm{query}_1$ $\mathrm{query}_2$ $\vdots$ $\mathrm{query}_Q$

Each query has one of the three formats described in the statement.

Output

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 $s$ is the nickname and $y$ is the judging time. If there is no record, print -1 on one line.

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

$s\ c$

where $s$ is the nickname and $c$ is the solved count. If there is no user, print -1 on one line.

Do not print additional separators between outputs of different queries or test cases.

Constraints

$1 \le T \le 200\,000$ .
$1 \le N,Q \le 200\,000$ .
The sum of $N$ over all test cases does not exceed $200\,000$ .
The sum of $Q$ over all test cases does not exceed $200\,000$ .
$0 \le t \le 10^9$ .
Within each test case, query times $t$ are given in nondecreasing order.
In a type- $1$ query, $1 \le i \le N$ .
In type- $1$ and type- $2$ queries, $1 \le x \le 10^9$ .
In a type- $1$ query, $1 \le y \le 10^9$ .
Nickname $s$ consists only of lowercase English letters and has length from $1$ to $20$ .
Two different users never use the same nickname.
Every number in the input is an integer.

Subtasks

#	Score	Constraints
1	10	$Q \le 2\,000$ in every test case. The sum of $Q$ over all test cases does not exceed $2\,000$ .
2	12	$N=1$ . There is no type- $3$ query.
3	18	There is no type- $3$ query.
4	15	$N=1$ . There is no type- $2$ query. Every $(\mathrm{nickname},\mathrm{problem})$ pair is submitted at most once.
5	20	Every $(\mathrm{nickname},\mathrm{problem})$ pair is submitted at most once.
6	25	No additional constraints.

Samples

Input

1
10
0 1 1 5 alice
0 2 1 3 bob
2 1
3 1
3 2 2 2 alice
4
5 1
5
5 1 1 1 carol
6 1

Output

-1
bob 3
bob 1
bob 3
alice 5
alice 2
bob 1
carol 1
bob 3
alice 5

bob's submission starts on server 2 at time $0$ and finishes at time $3$ . alice's submission to problem 1 finishes at time $5$ , and her submission to problem 2 also finishes at time $5$ , so she has solved two problems at that time. carol's submission starts at time $5$ and finishes at time $6$ . At time $6$ , the problem-1 ranking is carol, bob, alice because smaller judging time ranks higher.

Editorial

View editorial