Se da un arreglo $A=[a_1,a_2,\dots,a_n]$ de longitud $n$.

Para un intervalo $[x,y]$ ($1\le x\le y\le n$), si es posible elegir tres índices distintos entre sí $i,j,k\ (x\leq i\lt j\lt k\leq y)$ de entre los índices $x,x+1,\dots,y$ tales que sus valores correspondientes puedan formar las longitudes de los tres lados de un triángulo, es decir, $a_i+a_j\gt a_k, a_i+a_k\gt a_j, a_j+a_k\gt a_i$, entonces se dice que $[x,y]$ es un intervalo triangular. En particular, un intervalo de longitud menor que $3$ nunca es un intervalo triangular.

Ahora se necesita soportar $q$ operaciones, donde cada operación es de uno de los dos tipos siguientes:

• Operación de tipo 1: $1\ p\ v\ (1\leq p\leq n, 1\leq v\leq 10^{18})$, que modifica $a_p$ a $v$.
• Operación de tipo 2: $2\ l\ r\ (1\leq l\leq r\leq n)$, que consulta cuántos de todos los intervalos $[x,y]$ que satisfacen $l\le x\le y\le r$ son intervalos triangulares.

Por favor, para cada operación de tipo 2, imprima el resultado estadístico correspondiente.

Entrada

Cada prueba contiene múltiples casos de prueba. La primera línea contiene el número de casos de prueba $T$ ($1\le T\le 10^4$).

Para cada caso de prueba:

• La primera línea contiene dos enteros $n$, $q$ ($1\leq n\leq 10^6,~1\leq q\leq 2\times 10^4$), que representan la longitud de la secuencia $A$ y el número de consultas.
• La segunda línea contiene $n$ enteros $a_1,a_2,\ldots,a_n$ ($1\le a_i\le 10^{18}$), que representan los elementos de la secuencia dada $A$.
• Las siguientes $q$ líneas contienen cada una $3$ enteros que representan una operación; el formato de entrada de ambos tipos de operaciones se puede ver en la descripción del problema.

Se garantiza que la suma de $n$ en todos los casos de prueba no supera $10^6$, la suma de $q$ en todos los casos de prueba no supera $2\times 10^4$, y que cada caso de prueba tiene al menos una operación de tipo 2.

Salida

Para cada operación de tipo 2, imprima el número de intervalos triangulares dentro de $[l,r]$.

Ejemplos

Entrada 1

2
6 5
3 4 5 1 1 100
2 1 3
2 4 6
1 6 1
2 4 6
2 1 6
3 1
1 1 1
2 1 3

Salida 1

1
0
1
7
1