题目描述

《贪玩蓝月》是目前最火爆的网页游戏。在游戏中每个角色都有若干装备，每件装备有一个特征值 $w$ 和一个战斗力 $v$。在每种特定的情况下，你都要选出一个特征值对 $p$ 取模后在一段范围内的装备，而角色死亡时自己的装备会爆掉。每个角色的物品槽可以看成一个双端队列，得到的装备会被放在两端，自己的装备爆掉也会在两端被爆。

现在我们有若干种事件和询问，如下所示：

• IF w v：在前端加入一件特征值为 $w$ 战斗力为 $v$ 的装备
• IG w v：在后端加入一件特征值为 $w$ 战斗力为 $v$ 的装备
• DF：删除最前端的装备
• DG：删除最后端的装备
• QU l r：在当前的装备中选取一件装备，他的特征值对 $p$ 取模后在 $[l,r]$ 中，并且该装备的战斗力最大

为了锻炼你的水平，请尽量使用在线做法。

输入格式

第一行一个整数表示测试点编号。

第二行两个整数 $m$ 和 $p$，分别表示操作数和模数。

接下来每一行一个操作，如题目描述中所述，有五种操作，在前后加或删一件物品或者询问。

输出格式

对于每个询问，输出一行，表示在当前装备中选取一件特征值对 $p$ 取模后在 $[l,r]$ 的装备，满足该装备战斗力最大。如果没有合法方案，输出 -1。

0
11 10
QU 0 0
QU 1 9
IG 14 7
IF 3 5
QU 0 9
IG 1 8
DF
QU 0 4
IF 1 2
DG
QU 2 9

0
-1
7
8
7