学习到存有用的东西
top就直接top到前面预留的位置去

感觉用伸展树写，不好写.... 

/*
    题意：n<=10^8个人，q<=10^5个操作
    操作有三种：
                top x   将编号为x的调到队列前
                query x  查询编号为x的位置
                rank  x  位置在x出的编号
    n很大，存不下，考虑存q  只存要操作的编号，离散化

    然后留q个位置给未来的top
    首先在[q+1q+n] (n为不同的人数) 每个点存A[q+i]=num[i]-num[i-1]
    也即表示在位置q+i处有num[i]-num[i-1]个人，只不过用编号num[i]的人来表示而已
    top x 就移动x到前面，然后原来位置的人数-1，新位置+1，还有更新pos[],peo[]
    query x 即sum(peo[xx])
    rank x 先用findK()找到最接近x的且大于等于x的位置，调整下答案即可

    这一切用树状数组做
    pos[i]表示在数组i处是谁（原来的编号）
    peo[i]表示编号为i（压缩后的编号）的位置
*/
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int MAXN = 100010;

struct OP
{
    char cmd[10];
    int x;
}op[MAXN];

int N;
int num[MAXN];//for compress
int pos[MAXN*2],peo[MAXN];//pos[i] = who     peo[i] = where
int C[2*MAXN];//,A[2*MAXN];//    A[i] = number of people at pos[i]

inline int lowbit(int x)
{
    return x&(-x);
}
inline void add(int p,int x)
{
    while(p<=N)
    {
        C[p]+=x;
        p+=lowbit(p);
    }
}
inline int sum(int p)
{
    int ans = 0;
    while(p>0)
    {
        ans+=C[p];
        p-=lowbit(p);
    }
    return ans;
}
int findK(int K)//find the first one >=K
{
    int pos = 0,cnt = 0;
    for(int i=17;i>=0;i--)
    {
        pos+=(1<<i);
        if(pos>=N||cnt+C[pos]>=K)pos-=(1<<i);
        else cnt+=C[pos];
    }
    return pos+1;
}
int main()
{
    //freopen("in","r",stdin);
    int T,t=1,n,q;
    for(scanf("%d",&T);T--;)
    {
        printf("Case %d:\n",t++);
        scanf("%d%d",&n,&q);
        num[0]=0;
        for(int i=0;i<q;i++)
        {
            scanf("%s%d",op[i].cmd,&op[i].x);
            num[i+1]=op[i].x;
        }
        sort(num+1,num+1+q);
        n=unique(num+1,num+1+q)-(num+1);
        N = q+n;
        fill(C,C+N+1,0);
        //fill(A,A+N+1,0);
        for(int i=1;i<=n;i++)
        {
           // A[q+i]=num[i]-num[i-1];
            add(q+i,num[i]-num[i-1]);
            pos[q+i]=num[i];
            peo[i]=q+i;
        }
        int top=q;
        for(int i=0;i<q;i++)
        {
            if(strcmp(op[i].cmd,"Top")==0)
            {
                int x=lower_bound(num+1,num+1+n,op[i].x)-num;
                add(peo[x],-1);
                pos[peo[x]]--;
                peo[x]=top;
                add(peo[x],+1);
                pos[top]=op[i].x;
                top--;
            }
            if(strcmp(op[i].cmd,"Rank")==0)
            {
                int K=op[i].x;
                int p=findK(K);//
                int sp=sum(p);
                if(sp==K)printf("%d\n",pos[p]);
                else printf("%d\n",pos[p]-(sp-K));
            }
            if(strcmp(op[i].cmd,"Query")==0)
            {
                int x=lower_bound(num+1,num+1+n,op[i].x)-num;
                printf("%d\n",sum(peo[x]));
            }    
        }
    }
    return 0;
}