Description

OIER is a large specialized software company with tens of thousands of employees. As a cashier, one of my tasks is to record every employee’s salary. It used to be a decent job, but what is depressing is that our boss is capricious and frequently adjusts employees’ salaries. If he is in a good mood, he may add the same amount to every employee’s salary. Conversely, if he is in a bad mood, he may deduct the same amount from the salaries of all employees currently in the company. I really do not know what else he does besides adjusting salaries.

Frequent salary adjustments make employees unhappy, especially during collective deductions. Once an employee finds that his salary has fallen below the contractually agreed lower bound, he will immediately leave the company and never return. The lower bound is uniformly defined for all employees. Whenever someone leaves, I must delete his salary record from the computer. Similarly, whenever the company hires a new employee, I must create a new salary record for them.

The boss often asks me about the salary status. He does not ask about the salary of any specific employee, but instead asks for the salary of the $k$-th highest employee at the moment. Every time he does that, I have to sort tens of thousands of employees and then tell him the answer.

Alright, now you know a lot about my job. As you guessed, I want you to write a salary statistics program. How about it, not too hard, right?

If an employee’s initial salary is below the minimum wage threshold, they are not included in the final tally.

Description

Input

The first line contains two integers $n$ and $\min$. Here, $n$ is the number of commands that follow, and $\min$ is the lower bound of the salary.

Each of the next $n$ lines contains a character $x$ and an integer $k$, representing one command. The command can be one of the following four types:

• I k Create a new salary record with initial salary $k$. If the initial salary is below the lower bound, the employee leaves immediately.
• A k Add $k$ to every employee’s salary.
• S k Subtract $k$ from every employee’s salary.
• F k Query the $k$-th highest salary.

Initially, the company has no employees.

Input Format

The first line contains two integers $n$ and $\min$.

Each of the following $n$ lines contains a character $x$ and an integer $k$, representing one command of the following four types:

• I k Insert a new employee with initial salary $k$. If $k < \min$, the employee leaves immediately.
• A k Add $k$ to all current employees’ salaries.
• S k Subtract $k$ from all current employees’ salaries. Any employee whose salary falls below $\min$ leaves immediately and is removed from the records.
• F k Query the $k$-th highest salary among current employees.

Initially, there are no employees in the company.

Output Format

For each F command, output one line containing a single integer: the current $k$-th highest salary. If $k$ is greater than the number of current employees, output $-1$.

The last line outputs a single integer: the total number of employees who have left the company.

Please note that employees whose initial salary is below the lower bound do not count as having left.

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

10
20
-1
2

Hint

Constraints

• The number of I commands does not exceed $10^5$.
• The total number of A and S commands does not exceed $100$.
• The number of F commands does not exceed $10^5$.
• The adjustment amount for each salary update does not exceed $10^3$.
• A new employee’s salary does not exceed $10^5$.
• $0 \leq n \leq 3 \times 10^5$, $0 \leq \min \leq 10^9$, and all input numbers are within the 32-bit signed integer range.

Translated by ChatGPT 5