import java.io.*;
import java.util.*;

public class Problem_1439 implements Runnable{
    public static void main(String []args){
        new Thread(new Problem_1439()).start();
    }
    public void run(){
        try{
            reader = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
            solve();
        }catch(IOException e){
            throw new IllegalStateException(e);
        }
    }

    int nextInt()throws IOException{
        reader.nextToken();
        return (int)reader.nval;
    }

    boolean nextType()throws IOException{
        reader.nextToken();
        String s = reader.sval;
        if (s.length()!=1 && s.charAt(0)!='L' && s.charAt(0)!='D'){
            for (int i = 0; i< 1000000000;i++)System.out.println("ERORO");
        }
        return reader.sval.charAt(0)=='L';
    }

    int n, m;

    StreamTokenizer reader;

    final int MAX_N = 211111;

    class node{
        int left, right;
        int lleft, rright;
        int x, y;
        int size;

        node(){
            left = right= x = y = size =  lleft = rright = 0;
        }
    }
    node tree[];
    int g[];
    int  lt, root;
    int i, j, c, k;
    int getSize(int root){
        return (root == 0 ) ? 0: tree[root].size;
    }




    int insert(int root, int x, int y){
        if (root == 0 || tree[root].y <= y){

            lt++;
            //tree[lt] = new node();
            tree[lt].left   = 0;
            tree[lt].right  = 0;
            tree[lt].lleft  = lt;
            tree[lt].rright = lt;
            tree[lt].x = x;
            tree[lt].y = y;

            if (root > 0){
                if (tree[root].x < x)tree[lt].left = root; else tree[lt].right = root;
            }
            tree[lt].size = 1 + getSize(tree[lt].left)+getSize(tree[lt].right);

            if (tree[lt].left > 0)tree[lt].lleft = tree[tree[lt].left].lleft;
            if (tree[lt].right > 0)tree[lt].rright = tree[tree[lt].right].rright;
            return lt;
        }else if (x > tree[root].x){
            tree[root].size ++;
            tree[root].right = insert(tree[root].right, x, y);

            tree[root].rright = tree[tree[root].right].rright;
            return root;
        }else {
            tree[root].size++;
            tree[root].left = insert(tree[root].left, x, y);

            tree[root].lleft = tree[tree[root].left].lleft;
            return root;
        }
    }
    int getId(int root, int k, int min){
        if (root == 0)return k;
        int sz = getSize(tree[root].left);
        int delta = tree[root].x - (min + sz + 1);
        //if (delta < k)return getId(tree[root].right, k, min + sz + 1);
        if (delta >= k){
            if (tree[root].left == 0)return k + min;
            int lright = tree[tree[root].left].rright;
            int delta2 = tree[lright].x - (min  + sz);
            if (delta2 < k)return k + min + sz;else return getId(tree[root].left, k, min);
        }else {
            if (tree[root].right == 0)return k + min + sz + 1;
            int rleft = tree[tree[root].right].lleft;
            int delta2 = tree[rleft].x - (min + sz + 2);
            if (delta2 >= k)return k + min + sz + 1; else return getId(tree[root].right, k , min + sz + 1);
        }
    }

    void solve()throws IOException{
        n = nextInt();
        m = nextInt();
        g = new int[ MAX_N+1];
        tree = new node[MAX_N + 1];
        for (i = 0; i<=MAX_N;i++){
            tree[i] = new node();

        }


        for (i = 1; i<=MAX_N;i++){
            k = 1 + new Random().nextInt(i);
            g[i] = g[k];
            g[k] = i;
        }
        root = 0;
        lt = 0;
        j = 0;

        boolean type;
        int mind, maxd, d;
        mind = 1000000000;
        maxd = 1;
        d = 0;
        for (i = 1; i<= m;i++){
            type = nextType();
            k = nextInt();
            if (k <= mind)k = k + 0;
            else if(k + d>=maxd )k+=d;
            else
            k  = getId(root, k, 0);

            if ( type ) {//L
                System.out.println(k);
            }else if (k<=n){//D
                j++;
                root = insert(root, k, g[j]);
                d ++;
                if (k <= mind)mind = k - 1;
                if (k >= maxd)maxd = k + 1;
            }

        }

    }
}