单调栈写法：

#include<bits/stdc++.h>
using namespace std;
int m, d, t = 0, size = 0;
pair<int, long long> stk[500010]; // 单调栈，first是位置，second是值
int main() {
    cin >> m >> d;
    int top = 0; // 栈顶指针
    
    for(int i = 0; i < m; i++) {
        char op;
        cin >> op;
        if(op == 'A') {
            long long n;
            cin >> n;
            n = (n + t) % d;
            size++;
            
            // 使用二分查找确定插入位置
            int left = 1, right = top, pos = top + 1;
            while(left <= right) {
                int mid = (left + right) / 2;
                if(stk[mid].second <= n) {
                    pos = mid;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            
            // 更新栈顶指针
            top = pos;
            stk[top] = {size, n};
        } 
        else if(op == 'Q') {
            int L;
            cin >> L;
            // 在栈中二分查找第一个位置 >= size-L+1的元素
            int target = size - L + 1;
            int left = 1, right = top, ans = top;
            
            while(left <= right) {
                int mid = (left + right) / 2;
                if(stk[mid].first >= target) {
                    ans = mid;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            
            t = stk[ans].second;
            cout << t << endl;
        }
    }
    return 0;
}