CASHIER - Blue Mary Needs Help Again

no tags 

Blue Mary is a cashier of a big company.The boss of this company is so annoying that he always increases or decreases wage of all workers.He increases all the workers' wage with a same number when he is happy or decreases all the worker's wage with a same number when he is depressed.

All the workers are angry with the boss, especially when he decreases their wage. A worker will leave the company and never go back when he finds his wage is lower than the least wage written on his contract. Blue Mary must delete the worker's files at that time. Another task she is to do is to build a file when a new worker joins this company.

The boss usually asks Blue Mary how much money the worker who gets the k-th most wage gets. Blue Mary is very tired with her work. Could you give her a hand?

Input

T

[the number of tests <= 10]

M MIN

[M is the number of commands below, MIN is the least wage]

C K

[C is one of the 4 characters I,A,S,F. I denotes that Mary should build a new file, and the new worker's wage is K(0<=K<=100000) at start.If K is less than MIN, the worker will not join the company. A denotes that the boss increases all the workers' wage with K(0<=K<=1000). S denotes that the boss decreases all the workers' wage with K(0<=K<=1000). F denotes that the boss asks Blue Mary a question: how much money does the worker who gets the k-th most wage get(K>0)?]

[M-1 other commands]

[other tests]

You may assume that:

  • The number of worker in the company at start is 0.
  • The number of command I is no more than 100000.
  • The total numner of command A and S is no more than 100.
  • The number of command F is no more than 100000.

Output

For each test case:

For each F command you must output one line contains a single integer which is the answer or -1 if K is more than the number of workers in the company at that time.

In the last line you must output a single integer - the number of workers who leave the company(excluded the ones who don't join the company)

Example

Sample Input:
1
9 10
I 60
I 70
S 50
F 2
I 30
S 15
A 5
F 1
F 2

Sample Output:
10
20
-1
2
Warning: large Input/Output data, be careful with certain languages

hide comments
Shikhar: 2016-01-06 14:29:08

A Mlog(N)^2 solution will give TLE. Time limit is too strict. Mlog(N) will work. :)


Added by:Fudan University Problem Setters
Date:2007-04-01
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO
Resource:Chinese National Olympiad in Informatics 2004,Day 1; translated by Blue Mary