1232 : 数据结构假象
Time Limit: 2 Sec Memory Limit: 256 Mb Submitted: 1 Solved: 1Description
给定一个长度为 \(n\) 的序列 \(a\) 和数字 \(k\)，你需要支持 \(m\) 次操作或查询：
\(\text{C t}\)：将最大的数字减去 \(k\)（如果有多个，则选择最左边的数字），此动作反复执行 \(t\) 次。
\(\text{A x}\)：询问序列中第 \(x\) 大的数字。
Input
第一行包含三个整数 \(n\)、\(m\) 和 \(k\) \((1\leq n,m\leq 5\times 10^5)\)。
接下来一行包含 \(n\) 个整数，表示序列 \(a\) \((1\leq a_i\leq 10^{18})\)。
接下来的 \(m\) 行中，每行包含一个字符和一个整数，表示一次操作或查询。
对于所有数据，保证 \(1\leq k,t\leq 10^{18}\)，\(1\leq x\leq n\)。
保证每次操作后的序列对所有 \(a_i\) 都满足 \(-10^{18}\leq a_i\leq 10^{18}\)。
Output
对于每个查询，输出一个整数表示答案。
Sample
3 5 5 7 3 9 A 3 C 1 A 2 C 2 A 3
3 4 -1