#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;
}