Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

HOMEM - Homem, elefante e rato

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

  • 1 ≤ N ≤ 10⁵
  • 0 ≤ M ≤ 10⁶
  • 1 ≤ A ≤ B ≤ N
  • 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

    Adicionado por:Wanderley Guimarăes
    Data:2012-05-26
    Tempo limite:0.100s-1.784s
    Tamanho do fonte:50000B
    Memory limit:1536MB
    Cluster: Cube (Intel G860)
    Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
    Origem:Primeira fase da Maratona de Programaçăo - 2011

    hide comments
    2016-10-12 06:31:19
    Na seção ENTRADA, segundo parágrafo, primeira frase há um erro.
    "As próximas M linhas contêm cada uma a descrição de uma operaçãao."

    A palavra "operaçãao" está incorreta.

    ^^
    2012-10-03 23:33:46 Tiago Reis [UFSCar]
    Dica: para C++, use o compilador g++ 4.3.2. Meu código tava tomando TLE quando compilado no g++ 4.0.0-8, mas passou quando compilei no outro

    Last edit: 2017-03-15 13:54:09
    2012-06-01 18:35:17 nomtb
    O tempo limite de 0.5s-10s năo é possível fazer em JAVA =(
    © Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.