1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int M=50004,P=505;
 5 
 6 int f[M][P][5];//背包 
 7 int stat[M][5],stag[M][5];//特征值 战斗值 
 8 int top[5];//栈顶 
 9 int m,p;
10 char a[10];
11 
12 void add(int d,int x,int y){//加入 
13     int to=++top[d];
14     stat[to][d]=x;stag[to][d]=y;
15     for(int i=0;i<p;i++){//进行一次背包 
16         if(i>=x) f[to][i][d]=f[to-1][i-x][d]+y;
17         else f[to][i][d]=f[to-1][p+i-x][d]+y;
18         f[to][i][d]=max(f[to-1][i][d],f[to][i][d]);
19     }
20 }
21 
22 int st[M][50];//ST表 
23 void init(int d){//ST表初始化 
24     for(int i=0;i<p;i++) st[i][0]=f[top[d]][i][d];
25     for(int k=1;k<=10;k++)
26         for(int i=0;i+(1<<k)-1<p;i++)
27             st[i][k]=max(st[i][k-1],st[i+(1<<(k-1))][k-1]);
28 }
29 
30 int get(int l,int r){//ST表查询区间最大值 
31     int k=0;
32     while(l+(1<<(k+1))-1<=r) k++;
33     return max(st[l][k],st[r+1-(1<<k)][k]);
34 }
35 
36 int ask(int l,int r){//询问 
37     int d=0,ma=-1;
38     if(top[0]==0&&top[1]==0){//都为空 
39         if(l==0) return 0;
40         else return -1;
41     }
42     if(top[d]==0) d=d^1;//令d不为空 
43     init(d^1);
44     for(int i=0;i<p;i++){
45         if(f[top[d]][i][d]<0) continue;
46         
47         int L=(l-i+p)%p,R=(r-i+p)%p,maxn;
48         if(L<=R) maxn=get(L,R);
49         else maxn=max(get(L,p-1),get(0,R));
50         
51         if(maxn<=0&&(i<l||i>r)) continue;//如果另一边为空且当前的特征值不在范围则舍去 
52         
53         ma=max(ma,f[top[d]][i][d]+maxn);
54     }
55     return ma;
56 }
57 
58 int main(){
59     int T;scanf("%d", &T);
60     
61     scanf("%d %d", &m, &p);
62     
63     for(int i=0;i<=m;i++) for(int j=1;j<p;j++) for(int k=0;k<=1;k++) f[i][j][k]=-1e10;//背包初始化 
64     
65     for(int iii=1;iii<=m;iii++){
66         int x,y,d=0;
67         scanf("%s", a+1);
68         if(a[2]=='G') d=1;//0为左 1为右 
69         
70         if(a[1]=='I'){//加 
71             scanf("%d %d", &x ,&y);
72             add(d,x%p,y);
73         } 
74         
75         else if(a[1]=='D'){//减 
76             if(top[d]==0){
77                 int mid=(top[d^1]+1)/2,to=top[d^1];top[d^1]=0;//(top[d^1]+1)/2是因为top[d^1]可能等于1  
78                 for(int i=mid;i;i--) add(d,stat[i][d^1],stag[i][d^1]);
79                 for(int i=mid+1;i<=to;i++) add(d^1,stat[i][d^1],stag[i][d^1]);
80             } 
81             top[d]--;
82         }
83         
84         else{//查询 
85             scanf("%d %d", &x, &y);
86             printf("%d\n", ask(x,y));
87         }
88     }
89     return 0;
90 }