G :: Not So Rapidshare

Time Limit: 2 Seconds    Memory Limit: 32768 KB

Nonlogius and Linearius are two brothers developing the next big file hosting service. They are currently implementing the upload request handling module. They want the module to be able to do the following tasks:

1.Receive new files to be processed and add them to the line of waiting files.

2.Pass the first file in the waiting line to the file saving module and report ID of that file.

3.Report size of the biggest file waiting to be processed.

4.Report sum of the sizes of all files waiting to be processed.

Unfortunately, the brothers could not implement this module efficiently; therefore, they have asked you to help them in doing this hard job.

 

Input

The input will have an integer TC (TC≤10), the number of test cases, in the first line. TC test cases will follow. First line of each test case will contain a single number Q (1≤Q≤2*10^6), the number of queries to be processed by the module. Each of the following Q lines will contain description of a query. Each query will start with a single character that is equal to “R”, “P”, “M”, or “S”. If the character is equal to “R” it will be followed by two integers ID and Size (0≤ID< 10^9 ,1≤Size≤ 10^9 ).

Description of each query is as follows:

   “R”: Receive a new file and its’ ID and size.

   “P”: Pass the first file in the waiting line to the other module, and report its’ ID.

   “M”: Report the maximum file size in the waiting line.

   “S”: Report sum of the sizes of all files in the line.

 

File IDs are guaranteed to be distinct in each test case.

 

 

 

Output

For each query of type “P”, “M”, or “S”, print the requested value in a single line. It is guaranteed that for all queries of type “P” or “M”, there will be at least one file in the waiting line. Note that if all queries are of type “R” in a test case, you don’t need to print anything for that test case.

 

 

Sample Input

3
1
R 131452 99999
7
R 7000 1100
S
R 3200 900
M
P
M
P
12
R 123 250
R 1543 1
M
S
P
P
S
R 131452 1500
R 11111 12000
M
P
S

Sample Output

1100
1100
7000
900
3200
250
251
123
1543
0
12000
131452
12000

Submit

Source: 12th Iran Nationwide Internet Contest III