Um dos estudos de Sir Isaac Maliki no século 17 estava aceso. Em seu experimento, ele teve uma tira de $N$ segmentos coloridos. Cada um desses segmentos inicialmente tinha uma cor $Ci$. Depois de alguns testes, ele percebeu algo muito interessante: quando ele focalizou essa tira em uma luz de cor $C$, todos os segmentos que tinham a cor $C$ refletiam essa cor e os segmentos que não tinham essa cor tornaram-se pretos. Após essa descoberta, ele começou a brincar com esse fato. Ele fez $Q$ operações neste intervalo: uma das operações era mudar a cor de um dos segmentos da tira e a outra operação era iluminá-lo com uma luz com alguma cor e contar quantos intervalos contíguos dela não eram pretos. Ele escreveu todas essas operações em um papel, junto com suas observações.Já no século 21, alguns pesquisadores universitários encontraram este artigo de Maliki, com suas notas. Porém, havia uma parte do papel que estava desgastada e ninguém conseguiu decifrar: as respostas para o segundo tipo de operação. A tarefa de descobrir essas respostas foi repassada para o instituto de informática dessa universidade e você, felizmente, faz parte desse instituto. Ajude-os escrevendo um programa que simule o experimento de Maliki, assumindo o fato de que o que ele descobriu é verdade e apoiando as consultas e alterações feitas.

Entrada

A primeira linha contém dois inteiros $N$, $Q$ ($1 \leq N, Q \leq 10^6$), indicando o tamanho da tira e o número de operações feitas por Maliki.

A segunda linha contém $N$ inteiros $Ci$ ($1\leq Ci\leq N$), indicando a cor inicial do $i$-ésimo segmento da tira.

Cada uma das $Q$ linhas seguintes descreve as perguntas e as mudanças, seguindo o formato:

• $1$ $X$ $C$ - Mude a cor do $X$-ésimo segmento da tira para a cor $C$ ($1 \leq X, C \leq N$). Pode ser que o segmento $X$ já tenha a cor $C$, não alterando a configuração da faixa.
• $2$ $C$ - Conte quantos intervalos contíguos da faixa atual não são pretos se iluminarmos com uma luz com cor $C$ ($1 \leq C \leq N$);