Phony
Description
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.
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}$
For each inquiry, print a line for the answer.
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.
3 5 5
7 3 9
A 3
C 1
A 2
C 2
A 3
3
4
-1