1232 : 数据结构假象

Description

给定一个长度为 \(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

Hint

Source

Author

SYSU