Nas Olimpíadas de Nisa e Idanha-a-Nova (ONI), um dos desportos mais famosos é o Lançamento do Peso com Precisão, que se realiza todas as semanas em Idanha-a-Nova. Neste jogo o objetivo é lançar o peso a uma distância o mais próxima possível de um inteiro fixo K. Todas as semanas, há um torneio entre os dois concelhos com vários jogadores, todos com uma distância de lançamento fixa e distinta entre si. Cada jogador tem uma força de lançamento que corresponde exatamente à distância que consegue lançar o peso, nem mais, nem menos. Sabe-se que todos os habitantes de Nisa têm uma força de lançamento superior a K e todos os habitantes de Idanha-a-Nova têm uma força de lançamento inferior a K.
Uma ronda do jogo consiste em dois jogadores de concelhos diferentes atirarem o peso e aquele que acertar mais perto do objetivo K continua a jogar e o outro é eliminado. Em caso de empate, ganha o jogador de Nisa pois é convidado, ou seja, o de maior força. Como as equipas de cada concelho não querem cansar os seus melhores jogadores, escolhem sempre o seu jogador que atira o peso a uma distância mais afastada do objetivo. Assim que um dos concelhos ficar sem jogadores, o torneio acaba e há uma grande festa no concelho vencedor.
Tu, como finalista das olimpíadas de informática, apercebes-te que consegues prever as vitórias de um jogador no próximo torneio e decides que vais lucrar com o teu conhecimento. Assim, decides informar quantas vitórias é que um certo Jogador vai ter aos munícipes que requisitarem os teus serviços (o jogador é escolhido pelo munícipes).
Por exemplo, consideremos K = 10 e que os jogadores têm forças {1, 3, 6, 7, 12, 18, 19, 25} o torneio seria o seguinte:
Neste caso, o jogador 12 ganhou 3 jogos, o jogador 3 ganhou 2, o jogador 1 e 19 ganharam ambos 1 e os restantes jogadores não ganharam um único jogo.
No entanto, a tua tarefa não é assim tão simples, pois de vez em quando os jogadores reformam-se e outros novos jogadores começam a participar nestes jogos, e tens de ter isto em conta. Assim, irás receber Q pedidos, cada um irá:
As forças dos jogadores ativos em qualquer altura são todas distintas entre si e nunca iguais a K e em qualquer altura há sempre pelo menos um jogador de Nisa e um jogador de Idanha-a-Nova.
Como também tens de treinar para as olimpíadas de informática, queres perder o mínimo de tempo possível a responder às perguntas para cada estado do conjunto de jogadores.
Dado um K fixo e um conjunto S de inteiros, (que representam as forças dos jogadores) que vai sendo alterado, descobrir a cada momento quantas rondas é que um dado inteiro ganha.
A primeira linha contém 3 inteiros separados por espaços, o objetivo K, o número de jogadores iniciais N e o número de pedidos Q, que podem ser uma pergunta, uma reforma ou um jogador novo.
A segunda linha contém N inteiros, Si, que correspondem aos N jogadores iniciais.
As Q linhas seguintes consistem, cada uma, num carácter e num inteiro X separados por espaços, no seguinte formato:
É garantido que sempre que um pedido é uma pergunta ou uma reforma, existe um jogador com força X e que sempre que o pedido é um novo jogador, não existe em S um jogador com força X.
Uma linha por cada pergunta (ou seja, por cada pedido ? X), com apenas um inteiro que corresponde a quantos jogos o jogador X ganhou no momento em que a pergunta foi feita.
São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:
| 1 ≤ K ≤ 1 000 000 000 | Distância objetivo | |
| 2 ≤ N ≤ 100 000 | Número de jogadores | |
| 1 ≤ Si ≤ 1 000 000 000 | Valores de forças de cada jogador | |
| 1 ≤ Q ≤ 100 000 | Número de pedidos |
Nota: É ainda garantido que:
Os casos de teste deste problema estão organizados em X grupos com restrições adicionais diferentes:
| Grupo | Número de Pontos | Restrições adicionais |
|---|---|---|
| 1 | 10 | N ≤ 100, Q ≤ 100 e K, Si ≤ 1 000 |
| 2 | 20 | N ≤ 10 000, Q ≤ 100 e K, Si ≤ 100 000 |
| 3 | 20 | K, Si ≤ 100 000 e apenas os jogadores mais fortes e mais fracos são adicionados/removidos * |
| 4 | 20 | K, Si ≤ 100 000 |
| 5 | 30 | - |
* Apenas os jogadores mais fortes e mais fracos serem adicionados/removidos significa que sempre que é feito um pedido de - é sempre relativa ou ao jogador mais fraco ou ao jogador mais forte, e cada pedido + adiciona um jogador mais fraco que todos os outros ou mais forte que todos os outros.
10 8 8 1 3 6 7 12 18 19 25 ? 1 ? 3 ? 6 ? 7 ? 12 ? 18 ? 19 ? 25
1 2 0 0 3 0 1 0
Este exemplo corresponde ao mencionado no enunciado.
15 10 12 3 34 6 14 21 26 9 13 18 10 ? 9 ? 14 + 25 + 8 - 18 ? 26 - 6 + 19 - 3 ? 21 + 40 ? 13
0 0 1 2 1
Quando as duas primeiras perguntas são feitas, os jogadores têm forças {3, 6, 9, 10, 13, 14, 18, 21, 26, 34}. O jogador 9 na sua única ronda perde contra o jogador 21 por desempate e o jogador 14 nunca chega a jogar.
Quando a terceira pergunta é feita, os jogadores têm forças {3, 6, 8, 9, 10, 13, 14, 21, 25, 26, 34}. O jogador 26 ganha contra o jogador 3 e perde contra o 6.
Quando a quarta pergunta é feita, os jogadores têm forças {8, 9, 10, 13, 14, 19, 21, 25, 26, 34}. O jogador 21 ganha contra os jogadores 8 e 9 e perde contra o jogador 10.
Quando a quinta pergunta é feita, os jogadores têm forças {8, 9, 10, 13, 14, 19, 21, 25, 26, 34, 40}. O jogador 13 ganha contra o jogador 19 e o torneio acaba.