记录编号	338582	评测结果	AAAAAAAAAA
题目名称	[JSOI 2008] 最大数	最终得分	100
用户昵称	rewine	是否通过	通过
代码语言	C++	运行时间	3.255 s
提交时间	2016-11-05 11:57:05	内存使用	11.76 MiB

#pragma warning(disable: 4786)
#define pro __attribute__((optimize("O3")))
#include <cstdio>
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <bitset>
#include <cstring>
#include <map> 
 
using namespace std;
 
#define Rep(_i,x,y) for(int (_i)=(x);(_i)<=(y);(_i)++)
typedef long long lg;
typedef unsigned long long ulg; 
 
namespace PROIO { 
template <class T>
  pro inline void read(T &x) {
	 register bool flag = 0;register char c;
	 while((c=getchar())>'9'||c<'0')
	   if(c == '-') flag = 1;
	 x = c-'0';
	 while((c=getchar())<='9'&&c>='0')
	  x = ((x<<1)+(x<<3))+c-'0';
	 if(flag) x = -x;  
   }
template <class T>
  pro inline void write(register T x) {
    if(x < 0) {
        putchar('-');  
        x = -x;  
    } 
	if(x >= 10)    
        write(x/10);
    putchar(x%10+'0');    
   }
}
 
using namespace PROIO;

const int MAXX = 300000;

#define OPEN

#define int long long
int m,d;
#define lh l,mid,o<<1
#define rh mid+1,r,(o<<1)|1
int ma[MAXX*5],tot = 0;
int n,t,x,y;

void upone(int l,int r,int o) {
	if(l == r) {
		ma[o] = n;
		return;
	}
	int mid = (l+r)>>1;
	if(tot <= mid) upone(lh);
	else upone(rh);
	ma[o] = max(ma[o<<1],ma[(o<<1)|1]);
}

void add() {
	cin >> n;
	n = (n+t)%d;
	tot++;
	upone(1,MAXX,1);
}

lg query(int l,int r,int o) {
	if(x <= l && y >= r) return ma[o];
	int mid = (r+l)>>1;
	lg tmp = -1<<20;
	if(x <= mid) tmp = query(lh);
	if(y > mid) tmp = max(tmp,query(rh));
	return tmp;
}

void Q() {
	int l;
    cin >> l;
	x = tot-l+1; y = tot;
	t = query(1,MAXX,1);
	cout << t <<endl;
}
 
pro void work() {
	ios::sync_with_stdio(0);
	cin >> m >> d;
	char c;
	while(m--) {
	    cin >> c; 
		if(c == 'A') add();
	    else Q();
	}
}

pro signed main() {
#ifdef OPEN
	freopen("bzoj_1012.in","r",stdin);
	freopen("bzoj_1012.out","w",stdout);
#endif
    work();
#ifdef OPEN
    fclose(stdin);
    fclose(stdout);
#endif 
    return 0;
}