Enunciado Bakugans

Problema A - Bakugans

Os Bakugans são pequenas esferas que quando são colocados em cima de cartas especiais, abrem-se, transformando-se em diferentes criaturas, tais como um dragão ou um escorpião. Cada Bakugan tem associada a si uma determinada quantidade de energia G que depois é usada quando combatem para descobrir qual é o mais forte. Por exemplo, podemos ter um Bakugan com 300G, outro de 400G e outro de 500G, sendo que o mais forte dos três seria neste caso o de 500G.

O Aniceto adora jogar com Bakugans e tem uma enorme colecção. Todos os dias leva alguns Bagukans para a escola, mostrando-os aos amigos e participando em animados combates. O Aniceto não leva contudo toda a colecção para a escola, preferindo antes escolher apenas alguns, nomeadamente os que têm maior energia, para que possa ser o mais poderoso em combate, e os que têm menor energia, para que os possa oferecer a outros amigos sem colocar em causa a sua capacidade de vencer futuros combates.

A colecção do Aniceto é tão grande que ele precisa de da tua ajuda para a manter. Em particular, ele tem de ser capaz de fazer as seguintes operações sobre a colecção:

    * Adicionar um Bakugan à colecção;
    * Remover o Bakugan com maior energia de toda a colecção.
    * Remover o Bakugan com menor energia de toda a colecção.

Por exemplo, imaginemos que o Aniceto inicialmente não tem nenhum Bakugan. Se começar por adicionar três Bakugans à colecção, um de 200G, outro de 600G e outro de 450G, passaria a deter uma colecção de Bakugans com as seguintes energias: {200, 600, 450}. Se o Aniceto quiser remover o Bakugan de menor energia, retira o de 200G e fica com a colecção {600, 450}. Se seguidamente quiser remover o de maior energia, retira o de 600G, e fica com a colecção {450}. Se adicionar agora um Bakugan de 700G, fica com uma colecção {450, 700}. Finalmente, se decidir agora remover o de menor energia, retira o de 450G e fica com uma colecção {700}.

Podes ajudar o Aniceto a gerir os seus Bakugans?
O Problema

Dado um conjunto de operações de adição e remoção de Bakugans, a tua tarefa é dizer quais os Bakugans que são retirados em cada operação de remoção. As operações de remoção possíveis correspondem a remover o Bakugan com maior ou menor energia de toda a colecção.
Input

Na primeira linha do input estão dois números inteiros A e R, separados por um espaço, indicando respectivamente a quantidade de adições de Bakugans (A) e a quantidade de remoções de mínimos ou máximos (R). Seguem-se exactamente A+R linhas, cada uma contendo um dos seguintes 3 formatos (sem as aspas):

    * "BAK E", onde E é um número, indicando uma operação de adição à colecção de um Bakugan de energia E.
    * "MIN", indicando uma remoção do Bakugan da colecção com menor energia;
    * "MAX", indicando uma remoção do Bakugan da colecção com maior energia;

Podem existir vários Bakugans com a mesma energia ao mesmo tempo na colecção, sendo que nesse caso é indiferente qual o Bakugan que é retirado. É garantido que existe sempre pelo menos um Bakugan na colecção quando uma operação de remoção é efectuada. Todas as operações são feitas pela ordem em que aparecem no input.
Output

O output deve ter exactamente R linhas. Em cada uma delas deve ser imprimido um único número inteiro indicando a energia do Bakugan retirado na operação de remoção respectiva, pela mesma ordem em que estas operações aparecem no input.
Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:
1 ≤ A ≤ 100 000 	      	Número de operações de adição
1 ≤ R ≤ 10 000 	      	Número de operações de remoção
1 ≤ E ≤ 1 000 000 	      	Energia de cada Bakugan
Nota sobre a avaliação

Para um conjunto de casos de teste valendo 40% dos pontos, a soma do número de operações de adição com o número de operações de remoção é inferior a 1000.
Exemplo de Input

4 3
BAK 200
BAK 600
BAK 450
MIN
MAX
BAK 700
MIN

Exemplo de Output

200
600
450