题目描述

给定一个正整数序列 $a_1,a_2,\ldots,a_n$，每个数都在 $0$ 到 $p-1$ 之间。最开始，序列为空。你需要依次处理 $m$ 个操作，操作分为两类：

• 添加操作：向序列末尾添加一个数；
• 询问操作：询问当前序列最后 $L$ 个数中的最大值。

对于添加操作 A t，实际加入序列的数为 $(t+a)\bmod p$，其中 $a$ 表示在该添加操作之前最后一次询问操作的答案。如果之前没有询问操作，则 $a=0$。

输入格式

第一行包含两个正整数 $m,p$，分别表示操作数和模数。

接下来 $m$ 行，每行表示一个操作：

• Q L 表示询问当前序列最后 $L$ 个数中的最大值；
• A t 表示向序列末尾添加一个数 $(t+a)\bmod p$。

第一个操作一定是添加操作。对于每个询问操作，保证 $L>0$ 且 $L$ 不超过当前序列长度。

输出格式

对于每个询问操作，输出一行一个整数，表示当前序列最后 $L$ 个数中的最大值。

样例

10 100
A 97
Q 1
Q 1
A 17
Q 2
A 63
Q 1
Q 1
Q 3
A 99

97
97
97
60
60
97

样例解释

序列变化和询问过程如下：

• 添加 $97$，序列为 $[97]$；
• 询问最后 $1$ 个数的最大值，答案为 $97$；
• 再次询问最后 $1$ 个数的最大值，答案为 $97$；
• 添加 $(17+97)\bmod 100=14$，序列为 $[97,14]$；
• 询问最后 $2$ 个数的最大值，答案为 $97$；
• 添加 $(63+97)\bmod 100=60$，序列为 $[97,14,60]$；
• 询问最后 $1$ 个数的最大值，答案为 $60$；
• 再次询问最后 $1$ 个数的最大值，答案为 $60$；
• 询问最后 $3$ 个数的最大值，答案为 $97$；
• 最后一次添加操作之后没有询问，因此没有对应输出。

来源

JSOI 2008，一本通 4.3 练习 1。

数据范围与提示

• $1\le m\le 2\times 10^5$
• $1\le p\le 2\times 10^9$
• $0\le t<p$