1 //OJ 1700 2 //by Cydiater 3 //2016.8.31 4 #include <iostream> 5 #include <cstdio> 6 #include <cstdlib> 7 #include <queue> 8 #include <map> 9 #include <ctime>10 #include <cmath>11 #include <cstdlib>12 #include <cstring>13 #include <string>14 #include <algorithm>15 using namespace std;16 #define ll long long17 #define up(i,j,n)        for(int i=j;i<=n;i++)18 #define down(i,j,n)        for(int i=j;i>=n;i--)19 const int MAXN=1e5+5;20 const int oo=0x3f3f3f3f;21 inline int read(){22     char ch=getchar();int x=0,f=1;23     while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}24     while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}25     return x*f;26 }27 int N,LIM,num,root=0,tol=0,ans=0,delta=0;28 char op;29 struct node{30     int siz,v,leftt,rightt,cnt,rnd;31 }t[MAXN];32 namespace solution{33     void updata(int k){34         t[k].siz=t[t[k].leftt].siz+t[t[k].rightt].siz+t[k].cnt;35     }36     void lefturn(int &k){37         int tt=t[k].rightt;t[k].rightt=t[tt].leftt;t[tt].leftt=k;38         t[tt].siz=t[k].siz;updata(k);k=tt;39     }40     void righturn(int &k){41         int tt=t[k].leftt;t[k].leftt=t[tt].rightt;t[tt].rightt=k;42         t[tt].siz=t[k].siz;updata(k);k=tt;43     }44     void insert(int &k,int x){45         if(k==0){46             tol++;k=tol;t[k].siz=t[k].cnt=1;47             t[k].v=x;t[k].rnd=rand();48             return;49         }50         t[k].siz++;51         if(t[k].v==x)t[k].cnt++;52         else if(x>t[k].v){53             insert(t[k].rightt,x);54             if(t[t[k].rightt].rnd<t[k].rnd)    lefturn(k);55         }else if(x<t[k].v){56             insert(t[k].leftt,x);57             if(t[t[k].leftt].rnd<t[k].rnd)    righturn(k);58         }59     }60     int del(int &k,int x){61         int tmp=0;62         if(k==0)                return 0;63         if(t[k].v<x){64             tmp=t[t[k].leftt].siz+t[k].cnt;65             k=t[k].rightt;66             return tmp+del(k,x);67         }else{68             tmp=del(t[k].leftt,x);69             t[k].siz-=tmp;70             return tmp;71         }72     }73     int query_num(int k,int x){74         if(k==0)                                return 0;75         if(x<=t[t[k].leftt].siz)                return query_num(t[k].leftt,x);76         else if(x>t[t[k].leftt].siz+t[k].cnt)    return query_num(t[k].rightt,x-(t[t[k].leftt].siz+t[k].cnt));77         else                                    return t[k].v+delta;78     }79     void slove(){80         N=read();LIM=read();81         up(i,1,N){82             scanf("%c",&op);num=read();83             if(op==‘I‘&&num>=LIM)insert(root,num-delta);84             if(op==‘A‘)delta+=num;85             if(op==‘S‘){delta-=num;ans+=del(root,LIM-delta);}86             if(op==‘F‘)printf("%d\n",num>t[root].siz?-1:query_num(root,t[root].siz-num+1));87         }88         printf("%d\n",ans);89     }90 }91 int main(){92     //freopen("input.in","r",stdin);93     //freopen("output.out","w",stdout);94     using namespace solution;95     slove();96     return 0;97 }