3854. [雅礼集训 2018 Day10] 贪玩蓝月

【题目描述】

   大渣好，我四渣渣辉，点一下，玩一年，装备不花一分钱，说话战斗，罩杯回收，找一基友，极限到手。

   $0$ 元 $VIP$，$3$ 天满级，一秒一刀 $999$，装备全爆 $666$，广告做得再牛，不如进服遛一遛！

   古天乐绿了，古天乐绿了，惊喜不断，月入上万！不花钱还赚钱的绿色游戏，等级能提现，装备换点钱！

《贪玩蓝月》是目前最火爆的网页游戏。在游戏中每个角色都有若干装备，每件装备有一个特征值 $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$。

【样例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

【样例1输出】

0
-1
12
8
9

【样例1说明】

一开始没有物品，那么可以不选，特征值价值为 $0$，不可能凑出非 $0$ 的特征值。

然后在后面加了一个特征值 $14$ 价值 $7$ 的装备，又在前面加了一个特征值 $3$ 价值 $5$ 的装备，询问特征值取模后为 $[0, 9]$ 的装备，那么全部选择价值为 $12$。

然后在后面加了一个特征值为 $1$ 价值为 $8$ 的装备，删除了最前面的装备（特征值 $3$ 价值 $5$），询问特征值取模后为 $[0, 4]$ 的装备，那么只选择特征值为 $1$ 价值为 $8$ 的装备，最大价值为 $8$。

最后又在前面加了一个特征值为 $1$ 价值为 $2$ 的装备，删除了最后面的装备（特征值 $1$ 价值 $8$），询问特征值取模后为 $[2, 9]$ 的装备，那么选择当前剩余的两件装备，价值和为 $9$。

【样例2/3】

点击下载样例2/3

【数据规模与约定】

【来源】