인터네셔널 OJ

인터내셔널 OJ에는 $N$개의 채점 서버가 있다. 채점 서버에는 $1,2,\cdots,N$번의 번호가 붙어 있다. 각 채점 서버는 하나의 채점 큐를 가지며, 한 번에 하나의 제출만 채점할 수 있다. 모든 제출의 결과는 AC이다.

제출이 특정 채점 서버의 큐에 삽입되면, 서버는 큐에 먼저 삽입된 제출부터 순서대로 채점한다. 서버가 비어 있다면 새로 삽입된 제출의 채점을 즉시 시작한다. 하나의 제출을 채점하는 동안에는 다른 제출을 채점할 수 없다. 제출 하나의 채점이 완료되면 결과는 같은 시각에 데이터베이스에 반영되며, 큐에 다음 제출이 존재하면 같은 시각에 바로 다음 제출의 채점을 시작한다.

인터내셔널 OJ에서는 두 종류의 랭킹을 제공한다.

각 문제에 대해 채점이 완료된 제출들은 다음 순서로 정렬된다.

• 채점 시간이 짧은 순서.
• 채점 시간이 같다면 채점 완료 시각이 빠른 순서.
• 채점 완료 시각도 같다면 제출 쿼리가 먼저 주어진 순서.

한 사용자가 같은 문제를 여러 번 제출했더라도 각각의 제출은 서로 다른 기록으로 취급한다.

사용자가 푼 문제 수는 채점 완료된 AC 제출을 하나 이상 보유한 서로 다른 문제의 개수이다. 같은 문제를 여러 번 제출해도 푼 문제 수는 한 번만 증가한다. 사용자들은 다음 순서로 정렬된다.

• 푼 문제 수가 많은 순서.
• 푼 문제 수가 같다면 현재의 푼 문제 수를 달성한 시각이 빠른 순서.
• 해당 시각도 같다면 닉네임의 사전순.

현재의 푼 문제 수를 달성한 시각은 사용자가 가장 최근에 새로운 문제를 처음 푼 제출의 채점 완료 시각이다. 아직 채점이 완료된 제출이 하나도 없는 사용자는 사용자 랭킹에 포함되지 않는다.

$Q$개의 쿼리를 순서대로 처리하라. 쿼리는 다음 세 종류이다.

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

시각 $t$에 $i$번 채점 서버의 큐에 문제 번호 $x$, 채점 시간 $y$, 제출자 닉네임 $s$인 제출을 삽입한다. 서버가 시각 $t$에 비어 있다면 제출의 채점을 즉시 시작한다.

$2\ t\ x$

시각 $t$까지 채점이 완료된 제출만 이용하여 $x$번 문제의 랭킹을 출력한다. 랭킹이 높은 제출부터 최대 $5$개를 출력한다. 각 제출은 닉네임과 채점 시간을 출력한다. 채점이 완료된 제출이 하나도 없다면 -1을 출력한다.

$3\ t$

시각 $t$까지 데이터베이스에 반영된 결과를 기준으로 사용자 랭킹을 출력한다. 랭킹이 높은 사용자부터 최대 $5$명을 출력한다. 각 사용자는 닉네임과 푼 문제 수를 출력한다. 랭킹에 포함되는 사용자가 한 명도 없다면 -1을 출력한다.

입력은 다음과 같은 형식으로 주어진다.

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

각 케이스는 다음과 같은 형식으로 주어진다.

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

각 쿼리는 문제에서 설명한 세 형식 중 하나이다.

각 테스트 케이스에서 $2$번 또는 $3$번 쿼리가 주어질 때마다 해당 쿼리의 결과를 쿼리 순서대로 출력한다.

$2$번 쿼리에서 출력할 기록이 존재하면, 랭킹이 높은 순서대로 최대 $5$개의 줄에 걸쳐

$s\ y$

형식으로 닉네임 $s$와 채점 시간 $y$를 출력한다. 기록이 없다면 -1을 한 줄에 출력한다.

$3$번 쿼리에서 출력할 사용자가 존재하면, 랭킹이 높은 순서대로 최대 $5$개의 줄에 걸쳐

$s\ c$

형식으로 닉네임 $s$와 푼 문제 수 $c$를 출력한다. 사용자가 없다면 -1을 한 줄에 출력한다.

서로 다른 쿼리 또는 테스트 케이스의 출력 사이에 별도의 구분자는 출력하지 않는다.

• $1 \le T \le 200\,000$.
• $1 \le N,Q \le 200\,000$.
• 모든 테스트 케이스에 대한 $N$의 합은 $200\,000$ 이하이다.
• 모든 테스트 케이스에 대한 $Q$의 합은 $200\,000$ 이하이다.
• $0 \le t \le 10^9$.
• 한 테스트 케이스 안에서 쿼리의 시각 $t$는 감소하지 않는 순서로 주어진다.
• $1$번 쿼리에서 $1 \le i \le N$이다.
• $1$번과 $2$번 쿼리에서 $1 \le x \le 10^9$이다.
• $1$번 쿼리에서 $1 \le y \le 10^9$이다.
• 닉네임 $s$는 영문 소문자로 이루어진 길이 $1$ 이상 $20$ 이하의 문자열이다.
• 서로 다른 사용자가 같은 닉네임을 사용하는 경우는 없다.
• 입력으로 주어지는 모든 수는 정수이다.