Guildas

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

A primeira linha de entrada contém um inteiro N e um inteiro M, representando a quantidade de jogadores e a quantidade de ações, respectivamente.

Em seguida haverá N inteiros $P_i$, onde o i-ésimo inteiro representa o número de pontos que o i-ésimo jogador tem, para todo $1\leq i\leq N$. Rafael é o jogador número 1, sempre.

Por último, haverá M linhas, contendo três inteiros cada, Q, A e B, 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.

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

Restrições

• $1 \leq N \leq 10^5$
• $1 \leq M \leq 5\cdot 10^5$
• $1 \leq P_i \leq 100$
• $1 \leq Q \leq 2$
• $1 \leq A,B \leq N$

Exemplos

ENTRADA	SAÍDA
5 5 5 3 4 3 2 1 1 2 1 3 4 2 2 4 1 4 5 2 1 3	1