1232 : 数据结构假象

时间限制Time Limit
2 秒Sec
内存限制Memory Limit
256 兆MB
提交次数Submitted
4 次Times
通过次数Solved
1 次Times

题目描述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

出题Author

SYSU