Salary Adjustment and Query

OIER Inc. is a large professional software company with tens of thousands of employees. As a cashier, one of my tasks is to manage each employee's salary. However, the boss’s mood swings have meant that salaries are frequently adjusted. When the boss is in a good mood, he adds the same amount to every employee’s salary. When in a bad mood, he deducts the same amount from all current employees’ salaries. If an employee’s salary falls below the contractually guaranteed minimum wage after a deduction, that employee immediately quits and his salary record is removed. New employees can be hired at any time, and when they join, their salary record is created (provided that their initial salary is not below the minimum wage threshold). Moreover, the boss often asks for the current kth highest salary. Your task is to write a salary management program that supports these operations.

Note: If an employee’s initial salary is below the minimum wage threshold, it is not recorded at all.

inputFormat

The input begins with three integers n, m and L, where n is the number of initial employees, m is the number of operations, and L is the minimum wage threshold.

The next line contains n integers, representing the initial salaries of the employees. Only those salaries that are at least L are recorded.

Then follow m lines, each containing an operation in one of the following formats:

• “A d”: Add an integer d to every current employee’s salary. Note that d can be positive (salary increase) or negative (salary deduction). After a deduction (d negative), any employee whose salary falls below L is removed immediately.
• “N wage”: A new employee is hired with salary wage. If wage is less than L, it is ignored.
• “Q k”: Query the kth highest salary among the current employees. If k is greater than the number of employees, output -1.

outputFormat

For each query operation (operation starting with 'Q'), output the kth highest salary on a separate line. If k is more than the number of current employees, output -1.

sample

5 6 1000
1200 800 1000 2000 1500
Q 2
A 200
Q 2
A -500
N 1800
Q 3

1500
1700
1200