Du får en array $A=[a_1,a_2,\dots,a_n]$ med längden $n$.

För ett intervall $[x,y]$ ($1\le x\le y\le n$), om man bland indexen $x,x+1,\dots,y$ kan välja tre parvis olika index $i,j,k\ (x\leq i\lt j\lt k\leq y)$ så att deras motsvarande värden kan utgöra längderna på de tre sidorna i en triangel, det vill säga $a_i+a_j\gt a_k, a_i+a_k\gt a_j, a_j+a_k\gt a_i$, så kallas $[x,y]$ ett triangelintervall. I synnerhet är ett intervall med längd mindre än $3$ aldrig ett triangelintervall.

Nu behöver du stödja $q$ operationer, där varje operation är en av följande två typer:

• Operation av typ 1: $1\ p\ v\ (1\leq p\leq n, 1\leq v\leq 10^{18})$, ändrar $a_p$ till $v$.
• Operation av typ 2: $2\ l\ r\ (1\leq l\leq r\leq n)$, frågar hur många av alla intervall $[x,y]$ som uppfyller $l\le x\le y\le r$ som är triangelintervall.

Skriv ut motsvarande resultat för varje operation av typ 2.

Indata

Varje test innehåller flera testfall. Den första raden innehåller antalet testfall $T$ ($1\le T\le 10^4$).

För varje testfall:

• Den första raden innehåller två heltal $n$, $q$ ($1\leq n\leq 10^6,~1\leq q\leq 2\times 10^4$), som anger längden på följden $A$ samt antalet frågor.
• Den andra raden innehåller $n$ heltal $a_1,a_2,\ldots,a_n$ ($1\le a_i\le 10^{18}$), som anger elementen i den givna följden $A$.
• De följande $q$ raderna innehåller var och en $3$ heltal som beskriver en operation; indataformatet för de två operationstyperna framgår av problembeskrivningen.

Det garanteras att summan av $n$ över alla testfall inte överstiger $10^6$, att summan av $q$ över alla testfall inte överstiger $2\times 10^4$, samt att varje testfall innehåller minst en operation av typ 2.

Utdata

För varje operation av typ 2, skriv ut antalet triangelintervall inom $[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