10731073 SUSTech Online Judge
Problem 1073 --Balanced Binary Tree

1073: Balanced Binary Tree

Time Limit: 2 Sec  Memory Limit: 512 MB
Submit: 1106  Solved: 663
[Submit][Status][Web Board]


In a company, there are thousands of employees.  Your work is to check the information about the salary. There is a minimum salary (it is the same for everyone). If someone's salary is less than this minimum salary, he/she will leave the company. There are n operations, and each operation is one of the following cases:

Insert x: a fresh man joins the company, whose salary is x.

Add x: increase one's salary by x.

Subtract x: reduce everyone's salary by x.

Query x: print the k-th maximum salary in this company.


At first, there is no employee in the company.


The first line will be an integer T, which is the number of test cases. (1 <= T <= 10). For each test case, the first line will be two integers n(1 <= n <= 105) and m(1 <= m <= 106), n is the number of operations, m is the minimum salary. For the following n lines, each line will be one of the following cases:

I x: Insert x.

A x: Add x.

S x: Subtract x.

Q x: Query x.


For each “Query”, print the k-th maximum salary in this company. If the number of employees is less than k, print “-1”. At last, print the number of employees who has left the company. We guarantee that no one will come back to the company after he (or she) leaves.

Sample Input

9 10
I 60
I 70
S 50
Q 2
I 30
S 15
A 5
Q 1
Q 2

Sample Output



Please find extra material to learn how to construct the balanced binary tree.