Gegeben ist ein Array $A=[a_1,a_2,\dots,a_n]$ der Länge $n$.

Wenn man für ein Intervall $[x,y]$ ($1\le x\le y\le n$) aus den Indizes $x,x+1,\dots,y$ drei paarweise verschiedene Indizes $i,j,k\ (x\leq i\lt j\lt k\leq y)$ auswählen kann, sodass ihre zugehörigen Werte die Seitenlängen eines Dreiecks bilden können, also $a_i+a_j\gt a_k, a_i+a_k\gt a_j, a_j+a_k\gt a_i$ gilt, dann nennt man $[x,y]$ ein Dreiecksintervall. Insbesondere ist ein Intervall mit einer Länge kleiner als $3$ niemals ein Dreiecksintervall.

Nun müssen $q$ Operationen unterstützt werden, wobei jede Operation eine der folgenden zwei Arten ist:

• Operation 1. Art: $1\ p\ v\ (1\leq p\leq n, 1\leq v\leq 10^{18})$, ändert $a_p$ zu $v$.
• Operation 2. Art: $2\ l\ r\ (1\leq l\leq r\leq n)$, fragt ab, wie viele der Intervalle $[x,y]$ mit $l\le x\le y\le r$ Dreiecksintervalle sind.

Bitte geben Sie für jede Operation 2. Art das entsprechende Ergebnis aus.

Eingabe

Jeder Testpunkt enthält mehrere Testfälle. Die erste Zeile enthält die Anzahl der Testfälle $T$ ($1\le T\le 10^4$).

Für jeden Testfall:

• Die erste Zeile enthält zwei ganze Zahlen $n$, $q$ ($1\leq n\leq 10^6,~1\leq q\leq 2\times 10^4$), die die Länge der Folge $A$ und die Anzahl der Abfragen angeben.
• Die zweite Zeile enthält $n$ ganze Zahlen $a_1,a_2,\ldots,a_n$ ($1\le a_i\le 10^{18}$), die die einzelnen Elemente der gegebenen Folge $A$ angeben.
• Die nächsten $q$ Zeilen enthalten jeweils $3$ ganze Zahlen, die eine Operation beschreiben; das Eingabeformat der beiden Operationsarten ist in der Aufgabenstellung beschrieben.

Es wird garantiert, dass die Summe von $n$ über alle Testfälle $10^6$ nicht überschreitet, die Summe von $q$ über alle Testfälle $2\times 10^4$ nicht überschreitet und jeder Testfall mindestens eine Operation 2. Art enthält.

Ausgabe

Geben Sie für jede Operation 2. Art die Anzahl der Dreiecksintervalle innerhalb von $[l,r]$ aus.

Beispiele

Eingabe 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

Ausgabe 1

1
0
1
7
1