beecrowd | 1527

Guildas

Por Cristhian Bonilha, UTFPR BR Brazil

Timelimit: 2

Rafael está jogando um novo e excitante jogo de RPG, e acaba de notar a existência de algo chamado Guilda. Para aqueles que não sabem, Guilda se trata de um grupo de jogadores que se unem com um objetivo em comum dentro do jogo, tirando assim vantagem do trabalho em equipe.

O jogo que Rafael joga tem um sistema de GVG (Guilda versus Guilda) bem disputado, e logo percebeu que deveria tomar algumas providencias para se sair bem nessas batalhas.

O sistema de GVG funciona da seguinte maneira: a batalha acontece entre duas guildas, e vence a guilda que tiver o maior número de pontos. O número de pontos de uma guilda é dado pela soma do número de pontos de todos os jogadores presentes na guilda. Cada jogador tem um número de pontos, que corresponde ao seu nível atual.

Considere que inicialmente, todos os jogadores fazem parte de uma guilda, contendo apenas o próprio jogador. A união entre duas guildas faz com que todos os jogadores de ambas as guildas passem a participar apenas de uma guilda, e a outra deixa de existir.

Dada uma lista de ações no decorrer do jogo, entre elas união entre duas guildas e batalhas entre duas guildas, diga o número de vezes em que a guilda em que Rafael estava saiu vitoriosa de uma batalha.

Entrada

Haverá diversos casos de teste. Cada caso de teste inicia com dois inteiros N e M (1 ≤ N ≤ 10⁵, 1 ≤ M ≤ 5 * 10⁵), representando o número de jogadores dentro do jogo, e o número de ações no decorrer do jogo, respectivamente.

Em seguida haverá N inteiros Pi (1 ≤ Pi ≤ 100), onde o i-ésimo inteiro representa o número de pontos que o i-ésimo jogador tem, para todo 1 ≤ iN. Rafael é o jogador número 1, sempre.

Em seguida, haverá M linhas, contendo três inteiros cada, Q, A e B (1 ≤ Q ≤ 2, 1 ≤ A, BN), representando o tipo da ação, e as duas guildas envolvidas na ação. Se Q for igual a 1, significa que a guilda que contém o jogador A e a guilda que contém o jogador B estão se unindo. Se Q for igual a 2, significa que a guilda que contém o jogador A e a guilda que contém o jogador B participarão de uma batalha.

O último caso de teste é indicado quando N = M = 0, o qual não deverá ser processado.

Saída

Para cada caso de teste imprima uma linha, contendo um inteiro, indicando o número de batalhas em que a guilda em que Rafael está participando ganhou uma batalha. Note que empates não são considerados vitórias.

Exemplo de Entrada Exemplo de Saída

5 5
5 3 4 3 2
1 1 2
1 3 4
2 2 4
1 4 5
2 1 3
0 0

1