Sherlock Holmes ha recibido un encargo muy delicado: un coleccionista de diamantes ha dispuesto sus preciadas gemas en una serie de vitrinas alineadas de manera consecutiva en su mansión. Cada vitrina contiene cierta cantidad de diamantes, pero algunas han sido movidas o intercambiadas por asistentes descuidados durante la noche.
Holmes necesita analizar cuidadosamente la colección: en algunos momentos desea conocer cuántas vitrinas contienen un número específico de diamantes dentro de un tramo de la exposición, y en otros, se da cuenta de que algunas vitrinas han sido reorganizadas y el número de diamantes ha cambiado. Tu tarea es ayudar a Holmes a mantener el control de la colección mientras resuelve estos misterios.
Más formalmente, tienes un array \(\text{A}\) de \(N\) enteros, donde \(A_i\) representa la cantidad de diamantes en la vitrina \(i\). Se te harán \(Q\) consultas de los siguientes tipos:
Tipo 1: \(1\) \(i\) \(x\) - indicar que el número de diamantes en la vitrina \(i\) se actualiza a \(x\), es decir, \(A_i = x\).
Tipo 2: \(2\) \(l\) \(r\) \(x\) - determinar cuántas vitrinas en el rango \([l, r]\) contienen exactamente \(x\) diamantes.
Entrada
La primera línea contiene dos enteros \(N\) y \(Q\) \((1 \le N, Q \le 2 \cdot 10^5)\).
La segunda línea contiene \(N\) enteros \(A_1, A_2, \dots, A_N\) \((1 \le A_i \le 10^9)\).
Las siguientes \(Q\) líneas describen las consultas en los formatos mencionados.
Salida
Imprime un único entero: la suma de los resultados de todas las consultas de tipo 2, es decir, la cantidad total de vitrinas contadas en todas las consultas donde se preguntaba por un número específico de diamantes.