#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

template <class T>
struct treap {
    private:
        struct xor_128 {
            unsigned long long x,y,z,w;
            xor_128(): x(198535678165727856), y(2378257282762967), z(51738523678237522), w(75175185715718) {}
            unsigned long long next() {
                unsigned long long t=x^(x<<11);
                x=y;y=z;z=w;
                return w=w^(w>>19)^t^(t>>8);
            }
        };

        struct node {
            T key;
            node *left, *right;
            unsigned long long priority;
            unsigned size;
        };

        typedef node *node_ptr;

        xor_128 rng;
        node_ptr root;

        unsigned long long next() {
            return rng.next();
        }

        unsigned size(node_ptr a) {
            if(a==NULL) return 0;
            else return a->size;
        }

        unsigned update_size(node_ptr &a) {
            if(a!=NULL) a->size=1+size(a->left)+size(a->right);
        }

        node_ptr new_node(T key) {
            node_ptr res=(node_ptr)malloc(sizeof(node));
            res->key=key;
            res->left=NULL;
            res->right=NULL;
            res->priority=next();
            res->size=1;
            return res;
        }

        node_ptr right_rotation(node_ptr y) {
            node_ptr x=y->left;
            node_ptr t2=x->right;
            y->left=t2;
            x->right=y;
            update_size(y);
            update_size(x);
            return x;
        }

        node_ptr left_rotation(node_ptr x) {
            node_ptr y=x->right;
            node_ptr t2=y->left;
            x->right=t2;
            y->left=x;
            update_size(x);
            update_size(y);
            return y;
        }

        bool find(node_ptr root, T key) {
            if(root==NULL) return false;
            if(key==root->key) return true;
            else if(key<root->key) return find(root->left,key);
            else return find(root->right,key);
        }

        node_ptr remove_it(node_ptr root) {
            assert(root!=NULL);
            if(root->left==NULL && root->right==NULL) return NULL;
            else if(root->left==NULL) {
                root=left_rotation(root);
                root->left=remove_it(root->left);
            }
            else if(root->right==NULL) {
                root=right_rotation(root);
                root->right=remove_it(root->right);
            }
            else {
                if(root->left->priority>root->right->priority) {
                    root=right_rotation(root);
                    root->right=remove_it(root->right);
                }
                else {
                    root=left_rotation(root);
                    root->left=remove_it(root->left);
                }
            }
            update_size(root);
            return root;
        }

        node_ptr insert(node_ptr root, T key) {
            if(root==NULL) return new_node(key);
            else if(key<root->key) {
                root->left=insert(root->left,key);
                if(root->left->priority<root->priority) root=right_rotation(root);
            }
            else {
                root->right=insert(root->right,key);
                if(root->right->priority<root->priority) root=left_rotation(root);
            }
            update_size(root);
            return root;
        }

        node_ptr erase(node_ptr root, T key) {
            if(root==NULL) return root;
            else if(root->key==key) {
                root=remove_it(root);
            }
            else if(key<root->key) root->left=erase(root->left,key);
            else root->right=erase(root->right,key);
            update_size(root);
            return root;
        }

        T kth(node_ptr root, unsigned k) {
            if(size(root->left)+1==k) return root->key;
            else if(size(root->left)>=k) return kth(root->left,k);
            else return kth(root->right,k-1-size(root->left));
        }

        unsigned count_less(node_ptr root, T k) {
            if(root==NULL) return 0;
            if(root->key==k) return size(root->left);
            else if(k<root->key) return count_less(root->left,k);
            else return 1+size(root->left)+count_less(root->right,k);
        }

        void inorder(node_ptr root) {
            if(root==NULL) return;
            inorder(root->left);
            cout<<"( "<<root->key<<" , "<<root->size<<" )"<<' ';
            inorder(root->right);
        }

    public:
        treap(): root(NULL) {}

        unsigned size() {
            return size(root);
        }

        bool find(T key) {
            return find(root,key);
        }

        void insert(T key) {
            root=insert(root,key);
        }

        void erase(T key) {
            root=erase(root,key);
        }

        T kth(unsigned k) {
            return kth(root,k);
        }

        unsigned count_less(T k) {
            return count_less(root,k);
        }

        void inorder() {
            inorder(root);
        }

        void clear() {
            root=NULL;
        }
};

int tests,current_case;
int n,q;
treap < int > t;

void message(int current_case) {
    //cerr<<"Case "<<current_case<<" solved!"<<endl;
    //fprintf(stderr, "Case %d solved!\n", current_case);
}

int get_kth(int k) {
    int left=0,right=n,middle;
    while(right-left>1) {
        middle=(left+right)>>1;
        if(middle-t.count_less(middle+1)>=k) right=middle;
        else left=middle;
    }
    return right;
}

int main() {
    //ios_base::sync_with_stdio(false);
    //cin.tie(NULL);
    int i,x;
    char type[4];

    tests=1;
    //scanf("%d", &tests);
    //cin>>tests;
    for(current_case=1;current_case<=tests;current_case++) {
        scanf("%d %d", &n, &q);
        t.clear();
        while(q--) {
            scanf("%s", type);
            if(type[0]=='D') {
                scanf("%d", &x);
                x=get_kth(x);
                t.insert(x);
            }
            else {
                scanf("%d", &x);
                printf("%d\n", get_kth(x));
            }
        }

		MESSAGE:
        message(current_case);
    }

    return 0;
}