#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=3e5+5;
int fa[N],ch[N][2],val[N],cnt[N],sz[N],rt,tot;
struct Splay{
    void maintain(int x) {sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+cnt[x];}
    bool get(int x) {return x==ch[fa[x]][1];}
    void clear(int x){
        fa[x]=ch[x][0]=ch[x][1]=val[x]=cnt[x]=sz[x]=0;
    }
    void rotate(int x){
        int y=fa[x],z=fa[y],chk=get(x);
        ch[y][chk]=ch[x][chk^1];
        if(ch[x][chk^1]) fa[ch[x][chk^1]]=y;
        ch[x][chk^1]=y;
        fa[y]=x,fa[x]=z;
        if(z) ch[z][y==ch[z][1]]=x;
        maintain(y),maintain(x);
    }
    void splay(int x,int goal=0){
        for(int f;(f=fa[x])!=goal;rotate(x))
            if(fa[f]!=goal) rotate(get(f)==get(x)?f:x);
        if(!goal) rt=x;
    }
    void ins(int k){
        // cout<<k<<endl;
        if(!rt){
            val[++tot]=k,cnt[tot]++;
            rt=tot,maintain(rt);
            // cout<<"over ins:"<<k<<endl;
            return ;
        }
        int cur=rt,f=0;
        while(true){
            // cout<<"continue ins:"<<k<<endl;
            // cout<<"node's id"<<cur<<' '<<tot<<endl;
            // cout<<"node's value"<<val[cur]<<endl;
            if(val[cur]==k){
                cnt[cur]++;
                maintain(cur),maintain(f);
                splay(cur);break;
            }
            f=cur,cur=ch[cur][val[cur]<k];
            if(!cur){
                val[++tot]=k,cnt[tot]++;
                fa[tot]=f,ch[f][val[f]<k]=tot;
                maintain(tot),maintain(f);
                splay(tot);break;
            }
        }
    }
    int rk(int k){
        int cur=rt,res=0;
        while(cur){
            if(k<val[cur]) cur=ch[cur][0];
            else {
                if(val[cur]==k) {splay(cur);return sz[ch[cur][0]]+1;}
                res+=sz[ch[cur][0]]+cnt[cur],cur=ch[cur][1];
            }
        }
        return res+1;
    }
    int kth(int k){
        int cur=rt;
        while(cur){
            if(ch[cur][0]&&k<=sz[ch[cur][0]]) cur=ch[cur][0];
            else{
                k-=sz[ch[cur][0]]+cnt[cur];
                if(k<=0) {splay(cur);return cur;}
                cur=ch[cur][1];
            }
        }
    }
    int pre(){
        int cur=ch[rt][0];
        while(ch[cur][1]) cur=ch[cur][1];
        return cur;
    }
    void del(int k){
        rk(k);
        if(cnt[rt]>1){
            cnt[rt]--;
            maintain(rt);return ;
        }
        if(!ch[rt][0]&&!ch[rt][1]){
            clear(rt),rt=0;
            return ;
        }
        int cur=rt;
        if(!ch[rt][0]){
            rt=ch[rt][1],fa[rt]=0;
            clear(cur),maintain(rt);
            return ;
        }
        if(!ch[rt][1]){
            rt=ch[rt][0],fa[rt]=0;
            clear(cur),maintain(rt);
            return ;
        }
        int x=pre();
        ch[x][1]=ch[cur][1],fa[ch[cur][1]]=x;
        clear(cur),maintain(rt);
    }
    void del_subtree(int cur){
        if(!cur) return ;
        del_subtree(ch[cur][0]);
        del_subtree(ch[cur][1]);
        clear(cur);
    }
    // void dfs(int cur){
    //     if(ch[cur][0]) dfs(ch[cur][0]);
    //     cout<<val[cur]<<' ';
    //     if(ch[cur][1]) dfs(ch[cur][1]);
    // }
}tree;
int Q,MIN,c,k;
int SZ,leave;
char opt[11];
#define inf 0x3f3f3f3f
int main(){
    freopen("P1486_2.in","r",stdin);
    freopen("P1486_2.out","w",stdout);
    scanf("%d%d",&Q,&MIN);
    tree.ins(inf);
    while(Q--){
        scanf("%s%d",opt,&k);
        // cout<<opt<<' '<<k<<endl;
        if(opt[0]=='I')
            if(k>MIN) tree.ins(k-c),SZ++;
        if(opt[0]=='A') c+=k;
        if(opt[0]=='S') {
            c-=k;
            tree.ins(MIN-c);
            SZ-=sz[ch[rt][0]];
            leave+=sz[ch[rt][0]];
            // cout<<"del less than "<<val[rt]<<endl;
            // tree.dfs(rt),puts("");
            tree.del_subtree(ch[rt][0]);
            ch[rt][0]=0,tree.maintain(rt);
            tree.del(MIN-c);
        }
        if(opt[0]=='F') 
            if(SZ<k) printf("-1\n");
            else printf("%d\n",val[tree.kth(SZ-k+1)]+c);
        // cout<<opt<<' '<<k<<' '<<SZ<<' '<<c<<endl;
        // tree.dfs(rt),puts("");
    }
    printf("%d\n",leave);
}

提交记录