P1198：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 200000 + 5;
int st[MAXN][20],Log2[MAXN];
int a[MAXN],n,D,lastAns,M;
void initST() {
    for (int i = 1; i <= n; ++i) st[i][0] = a[i];
    for (int j = 1; (1 << j) <= n; ++j) {
        for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
            st[i][j] = max(st[i][j - 1],st[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int query(int L,int R) {
    int k = Log2[R - L + 1];
    return max(st[L][k],st[R - (1 << k) + 1][k]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>M>>D;
    n = 0;
    lastAns = 0;
    Log2[0] = -1;
    for (int i = 1; i <= M; ++i) Log2[i] = Log2[i / 2] + 1;

    char op;
    int x;
    for (int i = 1; i <= M; ++i) {
        cin>>op;
        if (op=='A') 
		{
            cin>>x;
            a[++n] = (x + lastAns) % D;
            initST();
        } else if (op=='Q') {
            cin>>x;
            lastAns = query(n - x + 1,n);
            cout<<lastAns<<"\n";
        }
    }
    return 0;
}

ST表