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.
Please find extra material to learn how to construct the balanced binary tree.