Console

Limits 1s, 512 MB

Now it is time for Intra Aust Programming Contest Fall 2020! Aust CSE 40th Batch is organizing the contest this time.

Shoaib and Alam from CSE 40th Batch, are right now too busy regarding this contest. They are given the responsibility to manage problem sets from seniors, alumni and alter them. Also, they have to set two problems individually. While they were working on their problems, they were asked to build a console for all the judges of this contest to analyze the participant’s performance better. The console, they were asked to build should perform the following operations,

U T S P - The console will update that, Team T currently solved S problems with P amount of penalties.
Q 1 R - The console will print the name of the Rth ranked team.
Q 2 T - The console will print the rank of Team T.
Q 3 R - The console will print the number of problems solved by the Rth ranked team and their penalties.
Q 4 S - The console will print the number of teams that solved exactly S problems.

The contest will start very soon, but Shoaib is now busy adding some large test cases to his problem and Alam is updating the checker for his problem. So they are asking for your help. Can you write a program for the console that can perform all the operations quickly?

Input

The first line of input contains N, S, Q. Following Q lines will contain one of the five operations mentioned above in a single line.

$1 <=$ Number of operations, $Q <= 4*10^5$

$1 <=$ Number of teams, $N <= 10^5$

$1 <=$ Rank, $R<=N$

$1 <=$ Number of problems, $S<=20$

$1 <=$ Penalty by a team, $P<=10^8$

$1 <=$ Length of $T<=20$

It is guaranteed that no two or more teams will have the same solve count(number of solves) with the same amount of penalty for any given moment.

For each team, their solve count and penalty will always increase. For example, If a team solved 4 problems with 100 Penalties, then the next update of the team(if any) will be 5 problems with a penalty of more than 100.

Also, each team’s solve count will increase by 1 only per update.

It is guaranteed that each query will be valid.

Output

For each operation, print the answer(s) in a single line.

Sample

Input	Output
7 11 30 U CorporateMinistry 1 5 U CorporateMinistry 2 15 U TimePenaltyMatters 1 12 U AngurFoltok 1 14 U Onslaught 1 22 U AngurFoltok 2 40 U Legacy 1 20 U Griffins 1 21 U TimePenaltyMatters 2 26 U Persistenists 1 25 Q 1 2 Q 1 5 U Griffins 2 44 Q 1 5 Q 2 Onslaught Q 4 10 Q 4 2 Q 2 AngurFoltok Q 3 1 U Legacy 2 45 Q 4 3 U TimePenaltyMatters 3 56 Q 4 3 U TimePenaltyMatters 4 120 Q 1 1 Q 1 5 Q 1 3 Q 2 Persistenists Q 3 4 Q 4 1	TimePenaltyMatters Griffins Legacy 6 0 4 3 2 15 0 1 TimePenaltyMatters Legacy AngurFoltok 7 2 44 2

Input

Output

7 11 30
U CorporateMinistry 1 5
U CorporateMinistry 2 15
U TimePenaltyMatters 1 12
U AngurFoltok 1 14
U Onslaught 1 22
U AngurFoltok 2 40
U Legacy 1 20
U Griffins 1 21
U TimePenaltyMatters 2 26
U Persistenists 1 25
Q 1 2
Q 1 5
U Griffins 2 44
Q 1 5
Q 2 Onslaught
Q 4 10
Q 4 2
Q 2 AngurFoltok
Q 3 1
U Legacy 2 45
Q 4 3
U TimePenaltyMatters 3 56
Q 4 3
U TimePenaltyMatters 4 120
Q 1 1
Q 1 5
Q 1 3
Q 2 Persistenists 
Q 3 4
Q 4 1

TimePenaltyMatters
Griffins
Legacy
6
0
4
3
2 15
0
1
TimePenaltyMatters
Legacy
AngurFoltok
7
2 44
2

A rank list of programming contests is calculated with the following rules,

The team with the most solves will be at the top. If two or more teams have the same number of solves, the team with less penalty will be at the top.