On vous donne un tableau $A=[a_1,a_2,\dots,a_n]$ de longueur $n$.

Pour un intervalle $[x,y]$ ($1\le x\le y\le n$), s'il est possible de choisir trois indices deux à deux distincts $i,j,k\ (x\leq i\lt j\lt k\leq y)$ parmi les indices $x,x+1,\dots,y$ tels que leurs valeurs correspondantes puissent former les longueurs des trois côtés d'un triangle, c'est-à-dire $a_i+a_j\gt a_k, a_i+a_k\gt a_j, a_j+a_k\gt a_i$, alors $[x,y]$ est appelé un intervalle triangulaire. En particulier, un intervalle de longueur inférieure à $3$ n'est jamais un intervalle triangulaire.

Vous devez maintenant prendre en charge $q$ opérations, chaque opération étant de l'un des deux types suivants :

• Opération de type 1 : $1\ p\ v\ (1\leq p\leq n, 1\leq v\leq 10^{18})$, qui modifie $a_p$ en $v$.
• Opération de type 2 : $2\ l\ r\ (1\leq l\leq r\leq n)$, qui demande combien d'intervalles $[x,y]$ vérifiant $l\le x\le y\le r$ sont des intervalles triangulaires.

Veuillez afficher le résultat correspondant pour chaque opération de type 2.

Entrée

Chaque test contient plusieurs cas de test. La première ligne contient le nombre de cas de test $T$ ($1\le T\le 10^4$).

Pour chaque cas de test :

• La première ligne contient deux entiers $n$, $q$ ($1\leq n\leq 10^6,~1\leq q\leq 2\times 10^4$), représentant la longueur de la séquence $A$ et le nombre de requêtes.
• La deuxième ligne contient $n$ entiers $a_1,a_2,\ldots,a_n$ ($1\le a_i\le 10^{18}$), représentant les éléments de la séquence donnée $A$.
• Les $q$ lignes suivantes contiennent chacune $3$ entiers représentant une opération. Le format d'entrée des deux types d'opérations est indiqué dans l'énoncé.

Il est garanti que la somme de $n$ sur tous les cas de test ne dépasse pas $10^6$, que la somme de $q$ sur tous les cas de test ne dépasse pas $2\times 10^4$, et que chaque cas de test comporte au moins une opération de type 2.

Sortie

Pour chaque opération de type 2, affichez le nombre d'intervalles triangulaires dans $[l,r]$.

Exemples

Entrée 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

Sortie 1

1
0
1
7
1