SPOJ Brasil

Um jogo muito popular na Nlogônia é o Homem, Elefante e Rato. Ele é tipicamente jogado com apenas dois jogadores, e funciona da seguinte forma: cada jogador secretamente escolhe um dos três símbolos e, após uma contagem regressiva, ambos revelam simultaneamente o símbolo escolhido através de sinais manuais, estendendo a sua frente uma das mãos sinalizando sua escolha.

O Homem é representado pela mão fechada, como a cabeça de um homem. O Elefante é representado pela mão aberta, exibindo os cinco dedos, como a pata do elefante nlogonense. Por fim, o Rato é representado pela mão fechada, com o dedo indicador e o dedo médio esticados, como as orelhas do pequeno animal.

Para determinar o vencedor é muito simples: o Homem sempre perde para o Elefante (pois é esmagado debaixo de sua pata), o Elefante sempre perde para o Rato (pois tem medo dele e foge correndo) e o Rato sempre perde para o Homem (que espalha ratoeiras para capturá-lo). Se dois jogadores utilizarem o mesmo símbolo, ocorre um empate e joga-se novamente.

Os habitantes da Nlogônia, que são estrategistas natos de Homem, Elefante e Rato, utilizam a seguinte técnica no campeonato nacional, realizado todos os anos: começam sempre jogando Homem até o momento em que este símbolo causa empates com a maioria dos oponentes. Eles então trocam sua estratégia para o símbolo que ganha daquele que usavam anteriormente. Assim, os jogadores vão mudar de Homem para Elefante, depois para Rato, depois de volta a Homem.

Para auxiliar um famoso competidor estrangeiro de um jogo parecido, que é quase, mas não completamente diferente de Homem, Elefante e Rato, você irá desenvolver um programa que contabiliza quantos jogadores irão utilizar cada símbolo.

Suponha que todos os N jogadores são dispostos em fila e identificados pela sua posição, de 1 a N. Seu programa deverá processar M comandos, de dois tipos: mudança de símbolo e contar a frequência dos símbolos. Ambos os comandos recebem um intervalo contíguo de jogadores na fila a serem considerados.

Entrada

A entrada é composta por diversos casos de teste. Cada caso de teste começa com uma linha contendo dois inteiros N e M que representam, respectivamente, o número de jogadores no campeonato e o número de operações.

As próximas M linhas contêm cada uma a descrição de uma operaçãao. Operações de mudança de estratégia serão representadas por uma linha da forma “M A B” onde A e B são inteiros. Os jogadores cuja estratégias serão alteradas são aqueles cuja posição na fila está entre A e B, inclusive.

Operações de contagem serão representadas por uma linha da forma “C A B” onde A e B são inteiros representando o intervalo de jogadores que deverão ser considerados na contagem. Levaremos em conta os jogadores cuja posição na fila está entre A e B, inclusive.

Saída

Para cada operação de contagem, imprima uma linha contendo três inteiros indicando respectivamente o número de símbolos Homem, Elefante e Rato que são usados pelos jogadores no intervalo dado. Imprima também uma linha em branco após cada caso de teste, inclusive após o ultimo caso de teste da entrada.

Restrições

Exemplos

Entrada

10 7 
C 1 10 
M 5 6 
C 5 6 
M 6 7 
C 4 8 
M 1 10 
C 1 10 
5 6 
M 1 5 
M 2 4 
M 1 2 
M 4 5 
C 1 5 
C 3 4 

Saída

10 0 0
0 2 0
2 2 1
1 7 2

2 0 3
1 0 1