记录编号	454149	评测结果	AAAAAAAAAA
题目名称	1844.[JSOI 2008] 最大数	最终得分	100
用户昵称	Hyoi_0Koto	是否通过	通过
代码语言	C++	运行时间	0.370 s
提交时间	2017-09-28 14:05:06	内存使用	1.55 MiB

/*written by 0koto*/
#prag\
ma GCC optimize("O3")
#include<cstdio>
#include<cctype>
#include<algorithm>
#define loop(i,j,k) for(int i=j;i<=k;++i)
typedef long long ll;
using namespace std;
inline void in(ll &x){
    x=0;int f=1;char c=getchar();
    while(!isdigit(c)){if(!(c-'-'))f=-1;c=getchar();}
    while (isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    x*=f;
}
inline void out(ll x){
    if(!x){putchar('0');return;}
    if(x<0)x=~x+1,putchar('-');
    char c[30]={0};
    while(x)c[++c[0]]=x%10+48,x/=10;
    while(c[0])putchar(c[c[0]--]);
}
const int maxm=200001;
ll m,ha,n,t,a[maxm],pos=0;
char qc;
int q[maxm],tail=1;
inline void q_push(ll x,int p){
    if(!(tail-1)){
        q[tail]=p,tail++;return;
    }
    while((tail-1)&&a[q[tail-1]]<x) tail--;
    q[tail]=p;tail++;
}
inline ll q_query(int p){
    int ans=lower_bound(q+1,q+tail,p)-q;
    return a[q[ans]];
}
inline int koto(){
	freopen("bzoj_1012.in","r",stdin);
	freopen("bzoj_1012.out","w",stdout);
    in(m),in(ha);
    loop(i,1,m){
        qc=getchar();while((qc-'A')&&(qc-'Q')) qc=getchar();in(n);
        if(qc-'Q') n=((ll)n+t)%ha,a[++pos]=n,q_push(n,pos);
        if(qc-'A') t=q_query(pos-n+1),out(t),putchar('\n');
    }
}
int zero=koto();
int main(){;}