#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma pack(1)
using namespace std;
using namespace __gnu_pbds;
#define TASK "test"
template<class Node_CItr,class Node_Itr,class Cmp_Fn,class _Alloc>
struct my_update_policy
{
virtual Node_CItr node_begin() const=0;
virtual Node_CItr node_end() const=0;
typedef int metadata_type;
int get(int x)
{
auto it=node_begin();
while(it!=node_end())
{
auto l=it.get_l_child();
auto r=it.get_r_child();
int T=x+1;
if(l!=node_end()) T+=l.get_metadata();
if(T<=**it)
{
it=l;
}
else
{
x=T;
it=r;
}
}
return x;
}
void operator()(Node_Itr it, Node_CItr end_it)
{
auto l=it.get_l_child();
auto r=it.get_r_child();
int left=0,right=0;
if(l!=end_it) left=l.get_metadata();
if(r!=end_it) right=r.get_metadata();
const_cast<int&>(it.get_metadata())=left+right+1;
}
};
tree<int,null_type,less<int>,rb_tree_tag,my_update_policy> me;
int main()
{
#ifndef ONLINE_JUDGE
freopen(TASK".in","r",stdin);
freopen(TASK".out","w",stdout);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
int n,m;
cin>>n>>m;
for(int i=0;i<m;i++)
{
char a;
int b;
cin>>a>>b;
if(a=='L')
cout<<me.get(b)<<"\n";
else
me.insert(me.get(b));
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNpbmNsdWRlIDxleHQvcGJfZHMvYXNzb2NfY29udGFpbmVyLmhwcD4KI2luY2x1ZGUgPGV4dC9wYl9kcy90cmVlX3BvbGljeS5ocHA+CiNwcmFnbWEgcGFjaygxKQoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKdXNpbmcgbmFtZXNwYWNlIF9fZ251X3BiZHM7CgojZGVmaW5lIFRBU0sgInRlc3QiCgp0ZW1wbGF0ZTxjbGFzcyBOb2RlX0NJdHIsY2xhc3MgTm9kZV9JdHIsY2xhc3MgQ21wX0ZuLGNsYXNzIF9BbGxvYz4Kc3RydWN0IG15X3VwZGF0ZV9wb2xpY3kKewogICAgdmlydHVhbCBOb2RlX0NJdHIgbm9kZV9iZWdpbigpIGNvbnN0PTA7CiAgICB2aXJ0dWFsIE5vZGVfQ0l0ciBub2RlX2VuZCgpIGNvbnN0PTA7CiAgICB0eXBlZGVmIGludCBtZXRhZGF0YV90eXBlOwoKICAgIGludCBnZXQoaW50IHgpCiAgICB7CiAgICAgICAgYXV0byBpdD1ub2RlX2JlZ2luKCk7CiAgICAgICAgd2hpbGUoaXQhPW5vZGVfZW5kKCkpCiAgICAgICAgewogICAgICAgICAgICBhdXRvIGw9aXQuZ2V0X2xfY2hpbGQoKTsKICAgICAgICAgICAgYXV0byByPWl0LmdldF9yX2NoaWxkKCk7CiAgICAgICAgICAgIGludCBUPXgrMTsKICAgICAgICAgICAgaWYobCE9bm9kZV9lbmQoKSkgVCs9bC5nZXRfbWV0YWRhdGEoKTsKICAgICAgICAgICAgaWYoVDw9KippdCkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgaXQ9bDsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHg9VDsKICAgICAgICAgICAgICAgIGl0PXI7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgcmV0dXJuIHg7CiAgICB9CgogICAgdm9pZCBvcGVyYXRvcigpKE5vZGVfSXRyIGl0LCBOb2RlX0NJdHIgZW5kX2l0KQogICAgewogICAgICAgIGF1dG8gbD1pdC5nZXRfbF9jaGlsZCgpOwogICAgICAgIGF1dG8gcj1pdC5nZXRfcl9jaGlsZCgpOwogICAgICAgIGludCBsZWZ0PTAscmlnaHQ9MDsKICAgICAgICBpZihsIT1lbmRfaXQpIGxlZnQ9bC5nZXRfbWV0YWRhdGEoKTsKICAgICAgICBpZihyIT1lbmRfaXQpIHJpZ2h0PXIuZ2V0X21ldGFkYXRhKCk7CiAgICAgICAgY29uc3RfY2FzdDxpbnQmPihpdC5nZXRfbWV0YWRhdGEoKSk9bGVmdCtyaWdodCsxOwogICAgfQp9OwoKdHJlZTxpbnQsbnVsbF90eXBlLGxlc3M8aW50PixyYl90cmVlX3RhZyxteV91cGRhdGVfcG9saWN5PiBtZTsKCmludCBtYWluKCkKIHsKICAgICNpZm5kZWYgT05MSU5FX0pVREdFCiAgICBmcmVvcGVuKFRBU0siLmluIiwiciIsc3RkaW4pOwogICAgZnJlb3BlbihUQVNLIi5vdXQiLCJ3IixzdGRvdXQpOwogICAgI2VuZGlmCiAgICBpb3M6OnN5bmNfd2l0aF9zdGRpbygwKTsKICAgIGNpbi50aWUoMCk7CiAgICBpbnQgbixtOwogICAgY2luPj5uPj5tOwoKICAgIGZvcihpbnQgaT0wO2k8bTtpKyspCiAgICB7CiAgICAgICAgY2hhciBhOwogICAgICAgIGludCBiOwogICAgICAgIGNpbj4+YT4+YjsKICAgICAgICBpZihhPT0nTCcpCiAgICAgICAgICAgIGNvdXQ8PG1lLmdldChiKTw8IlxuIjsKICAgICAgICBlbHNlCiAgICAgICAgICAgIG1lLmluc2VydChtZS5nZXQoYikpOwogICAgfQogfQo=