I. Phony
time limit per test
2 s
memory limit per test
512 MB
input
standard input
output
standard output

You are given a sequence of length $$$n$$$ and the number $$$k$$$, ask for support $$$m$$$ operations or inquiries:

  • $$$\text{C t}$$$: Let the largest number minus $$$k$$$ (the far left one if there is more than one), executed $$$t$$$ times.
  • $$$\text{A x}$$$: Ask for the $$$x$$$-th largest number.
Input

The first line contains three integer $$$n$$$, $$$m$$$ and $$$k$$$ $$$(1\leq n,m\leq 5\times 10^5)$$$.

The next line contains $$$n$$$ integers representing the sequence $$$a$$$ $$$(1\leq a_i\leq 10^{18})$$$.

Each of the following $$$m$$$ lines contains a character and an integer, indicating an operation or inquiry.

For all data guaranteed $$$1\leq k,t\leq 10^{18},\ 1\leq x\leq n$$$.

Ensure that the sequence after each operation for all $$$a_i$$$ satisfies $$$-10^{18}\leq a_i\leq 10^{18}$$$

Output

For each inquiry, print a line for the answer.

Example
Input
3 5 5
7 3 9
A 3
C 1
A 2
C 2
A 3
Output
3
4
-1