该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

附加文件

题目描述

Farmer John（以下简称 FJ）的奶牛要在直线上排队。一开始，这条线上没有任何奶牛，随着时间的推移，奶牛们会一个接一个地站到队伍的后边。

FJ 无法跟踪每一头奶牛，于是，他想让你来帮助他。

奶牛的入队方式很奇特。数据将会给出 $N$ 条指令，各占一行，分两种：

• Q K 表示查询牛队伍最后边的 K 头牛的最高牛的身高。数据保证 K 不超过牛队伍中的牛的总数。
• A x 表示将 x 加上 LastAns （LastAns 表示上一次 Q 操作的答案。如果之前没有 Q 操作，则 LastAns 为 0），并将结果 mod M （M 是一个给定值），将所得结果记为 H，即：H = (x + LastAns) mod M。然后让身高等于 H 的一头牛站到队伍的后边。

输入的命令一定是可以执行的。

输入格式

第 $1$ 行：两个整数 $N$ $M$

第 $2 \dots N+1$ 行：第 $i+1$ 行会有一条命令，有以下两种：

• Q K
• A x

输出格式

• 若干行：按输入顺序依次给出每个 Q 操作的答案，每个答案占一行。

样例输入

5 10
A 6
Q 1
A 7
Q 1
Q 2

样例输出

6
3
6

数据范围

$1 \le N \le 200,000$，$1 \le M < 2^{31}$，$0 \le x < 2^{31}$，