Problema B - Viagem Alternativa

Quando o Darth Vader tem a sua nave privada a arranjar, tem de recorrer aos serviços de transportes públicos. Na sua galáxia existe um serviço chamdo TIE Bus, uma nave semelhante a um TIE Fighter, mas mais comprida e com vários lugares. Um TIE Bus tem N lugares que são dispostos numa linha. Todos os lugares têm um número de 1 a N, referente à sua ordem na linha.

O Darth Vader observou que durante uma viagem iam entrando pessoas e saindo uma a uma, sem nenhuma ordem fixa. Cada pessoa entra inicialmente para um lugar fixo L que é indicado no bilhete que têm de ter para viajar no TIE Bus. Porém, ninguém gosta do lugar que lhes calha, ou porque é perto de uma janela, ou porque não é perto de uma janela, ou simplesmente porque conhecem alguém num lugar distante daquele e querem conversar. Por isso, cada pessoa escolhe um número P e procuram o P-ésimo lugar desocupado, ou seja, um lugar que tem P lugares desocupados entre ele e L. O P-ésimo lugar pode ser tanto antes como depois de L (ou o próprio L), depende da preferência do passageiro. Caso não existam P lugares desocupados (na direção preferida), o passageiro em questão amua e decide sair à procura de um novo TIE Bus. Notem que o próprio lugar L pode estar ocupado, pois alguém pode ter escolhido esse lugar anteriormente e que podem haver vários passageiros com o mesmo lugar L no bilhete independentemente de quando entram (a empresa é um bocadinho desorganizada).

Um possível exemplo deste comportamento é o seguinte:

1. O Darth Vader entra num TIE Bus de 5 lugares (nota que ele, como governador da galáxia, tem um lugar especial e não ocupa nenhum dos 5 lugares que estamos a estudar).
2. Entra um passageiro para o lugar 3 e decide procurar o 1º lugar desocupado depois do seu, que é o seu próprio lugar (aqui a definição de depois inclui o seu próprio lugar) e por isso fica no lugar 3.
3. Entra um passageiro para o lugar 1 e decide procurar o 3º lugar desocupado depois do seu, que é o lugar 4 (visto que o 3 está ocupado) e por isso fica no lugar 4.
4. O passageiro do lugar 3 chega ao seu destino e sai.
5. Entra um passageiro para o lugar 5 e decide procurar o 2º lugar desocupado antes do seu, que é o lugar 3 (visto que o 4 está ocupado) e por isso fica no lugar 3.

O Problema

Dado o tamanho N do TIE Bus e um número de mudanças de passageiros Q, a tua tarefa é descobrir onde fica cada um dos passageiros que entra. Uma mudança é uma entrada de um passageiro para um lugar L, um número escolhido P e um sentido de procura s (o sentido procura representa o sentido para onde esse passageiro se desloca, para depois ou antes de L) ou uma saída do passageiro de um lugar L.

Input

Na primeira linha vêm dois números inteiros separados por um espaço: N, o número de lugares e Q, o número de mudanças.

Seguem-se Q linhas indicando as mudanças. Cada uma delas começa por ter um caracter indicando o tipo de mudança. Se o caracter for um 'E', significa que entrou um passageiro e por isso segue-se um inteiro L, o seu lugar, um inteiro P, o número de lugares desocupados que o passageiro se desloca, e um segundo caracter que representa o sentido de procura (o sentido de procura pode ser 'D', que significa que procura um lugar depois do seu, ou 'A', que significa que procura um lugar antes do seu). Se o caracter for um 'S', significa que saiu um passageiro e por isso segue-se um inteiro L que representa o lugar de onde ele sai.

É garantido que todas as saídas e entradas de passageiros são válidas.

Output

Para cada mudança em que entre um passageiro, uma linha com um inteiro representando o lugar onde esse passageiro ficou ou, caso não encontre lugar, a palavra "Saiu" (sem as aspas).

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

Nota sobre a avaliação

Para um conjunto de casos de teste valendo 40% dos pontos, o valor de N será menor ou igual a 1 000 e Q e será menor que 100.

Para um conjunto de casos de teste valendo 60% dos pontos, o valor de Q será menor ou igual a 10 000.

Exemplo de Input 1

5 4
E 3 1 D
E 1 3 D
S 3
E 5 2 A

Exemplo de Output 1

3
4
3

Explicação de Input/Output 1

Este caso refere-se ao exemplo dado no enuncidado

Exemplo de Input 2

6 7
E 1 1 D
E 6 1 A
E 1 1 D
E 6 1 A
E 4 2 D
S 6
E 1 3 D

Exemplo de Output 2

1
6
2
5
Saiu
6