记录

#include <bits/stdc++.h> 
#define int long long
using namespace std;
int n,m,q,i,j,k,t0,t1,t2,t3,t4,t5,t6,t7,t8,t9,t10,t11,t12,t13,t14,t15,t16,t17,t18,t19,t20,t21,t22,t23,t24,t25,t26,t27,t28,t29,t30;
char ls;
struct dzpd 
{
	int l,r,maxx;
};
struct dzpd tr[800040];
int mod,a[200010];
int read();
void bd(int x, int l, int r);
void add(int x);
char getzl();
int getmax(int x, int l, int r);
void printx(int x);
signed main()
{
    scanf("%lld %lld",&m,&mod);
    bd(1,1,m);
	for (i = 1; i <= m; i++) 
	{
		//printf("n = %d\n",n);
		//cin >> ls;
		ls = getzl();
		if (ls == 'A')
		{
			scanf("%lld",&t1);
			t1 = ((t1 + t10) % mod);
			n++;
			a[n] = t1;
			add(1);
			/*
			k = 1;
			for (j = 1; j <= 4; j++)
			{
				for (; k <= pow(2,j)-1; k++)
				{
					printx(k);
				}printf("\n");
			}
			printf("\n\n");
			*/
		}
		else
		{
			scanf("%lld",&t3);
			if (t3 == 1)
			{
				t10 = a[n];
				printf("%lld\n",a[n]);
				continue;
			}
			t2 = n - t3 + 1;//printf("\n_______\n");
			t10 = getmax(1,t2,t3);
			printf("%lld\n",t10);
		}
	}
    return 0;
}
void bd(int x, int l, int r)
{
	tr[x].l = l, tr[x].r = r;
	if (l == r) 
	{
		tr[x].maxx = -99999999;
		return;
	}
	bd(x*2,l,(l+r)/2);
	bd(x*2+1,(l+r)/2+1,r);
	tr[x].maxx = max(tr[x*2].maxx,tr[x*2+1].maxx);
	return;
}
void add(int x)
{
	if (tr[x].l == tr[x].r) 
	{
		tr[x].maxx = t1; 
		return;
	}
	int mid = ((tr[x].l+tr[x].r) >> 1);
	if (n <= mid) add(x*2);
	else add(x*2+1); 
	tr[x].maxx = max(tr[x*2].maxx,tr[x*2+1].maxx);
	return;
}
int getmax(int x, int l, int r)
{
	if ((tr[x].l == l) && (tr[x].r == r))
	{
		return tr[x].maxx;
	}
	if (l >= tr[x*2+1].l)
	{
		return getmax(x*2+1,l,r);
	}
	if (r <= tr[x*2].r)
	{
		return getmax(x*2,l,r);
	}
	return max(getmax(x*2,l,tr[x*2].r),getmax(x*2+1,tr[x*2+1].l,r));
}
char getzl()
{
	char h;
	while(1)
	{
		h = getchar();
		if ((h != 'Q') && (h != 'A')) continue;
		return h;
	}
}
void printx(int x)
{
	printf("[%2d ",tr[x].l);
	if (tr[x].maxx == -99999999) printf("-i");
	else printf("%2d",tr[x].maxx);
	printf(" %2d]",tr[x].r);
}