Du får gitt en tabell $A=[a_1,a_2,\dots,a_n]$ med lengde $n$.

For et intervall $[x,y]$ ($1\le x\le y\le n$), hvis man blant indeksene $x,x+1,\dots,y$ kan velge tre parvis forskjellige indekser $i,j,k\ (x\leq i\lt j\lt k\leq y)$ slik at deres tilhørende verdier kan utgjøre lengdene til de tre sidene i en trekant, det vil si $a_i+a_j\gt a_k, a_i+a_k\gt a_j, a_j+a_k\gt a_i$, kalles $[x,y]$ et trekantintervall. Spesielt er et intervall med lengde mindre enn $3$ aldri et trekantintervall.

Nå må du støtte $q$ operasjoner, der hver operasjon er en av følgende to typer:

• Operasjon av type 1: $1\ p\ v\ (1\leq p\leq n, 1\leq v\leq 10^{18})$, endrer $a_p$ til $v$.
• Operasjon av type 2: $2\ l\ r\ (1\leq l\leq r\leq n)$, spør hvor mange av alle intervaller $[x,y]$ som oppfyller $l\le x\le y\le r$ som er trekantintervaller.

For hver operasjon av type 2 skal du skrive ut det tilsvarende resultatet.

Inndata

Hver test inneholder flere testtilfeller. Den første linjen inneholder antall testtilfeller $T$ ($1\le T\le 10^4$).

For hvert testtilfelle:

• Den første linjen inneholder to heltall $n$, $q$ ($1\leq n\leq 10^6,~1\leq q\leq 2\times 10^4$), som angir lengden på følgen $A$ og antall spørringer.
• Den andre linjen inneholder $n$ heltall $a_1,a_2,\ldots,a_n$ ($1\le a_i\le 10^{18}$), som angir elementene i den gitte følgen $A$.
• De neste $q$ linjene inneholder hver $3$ heltall som representerer én operasjon; inndataformatet for de to operasjonstypene fremgår av oppgavebeskrivelsen.

Det garanteres at summen av $n$ over alle testtilfeller ikke overstiger $10^6$, at summen av $q$ over alle testtilfeller ikke overstiger $2\times 10^4$, og at hvert testtilfelle har minst én operasjon av type 2.

Utdata

For hver operasjon av type 2, skriv ut antall trekantintervaller innenfor $[l,r]$.

Examples

Input 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

Output 1

1
0
1
7
1