Gefin er runa $A=[a_1,a_2,\dots,a_n]$ af lengd $n$.

Fyrir bil $[x,y]$ ($1\le x\le y\le n$), ef hægt er að velja þrjá innbyrðis ólíka vísa $i,j,k\ (x\leq i\lt j\lt k\leq y)$ úr vísunum $x,x+1,\dots,y$ þannig að samsvarandi gildi þeirra geti myndað lengdir þriggja hliða þríhyrnings, þ.e. $a_i+a_j\gt a_k, a_i+a_k\gt a_j, a_j+a_k\gt a_i$, þá kallast $[x,y]$ þríhyrningsbil. Sér í lagi er bil sem er styttra en $3$ aldrei þríhyrningsbil.

Nú þarf að styðja $q$ aðgerðir, þar sem hver aðgerð er af annarri hvorri af eftirfarandi tveimur gerðum:

• Aðgerð af gerð 1: $1\ p\ v\ (1\leq p\leq n, 1\leq v\leq 10^{18})$, breytir $a_p$ í $v$.
• Aðgerð af gerð 2: $2\ l\ r\ (1\leq l\leq r\leq n)$, spyr hversu mörg af öllum bilum $[x,y]$ sem uppfylla $l\le x\le y\le r$ eru þríhyrningsbil.

Vinsamlegast prentið út samsvarandi niðurstöðu fyrir hverja aðgerð af gerð 2.

Inntak

Hvert próf inniheldur mörg prófunartilvik. Fyrsta línan inniheldur fjölda prófunartilvika $T$ ($1\le T\le 10^4$).

Fyrir hvert prófunartilvik:

• Fyrsta línan inniheldur tvær heiltölur $n$, $q$ ($1\leq n\leq 10^6,~1\leq q\leq 2\times 10^4$), sem tákna lengd rununnar $A$ og fjölda fyrirspurna.
• Önnur línan inniheldur $n$ heiltölur $a_1,a_2,\ldots,a_n$ ($1\le a_i\le 10^{18}$), sem tákna stök gefnu rununnar $A$.
• Næstu $q$ línur innihalda hver um sig $3$ heiltölur sem tákna eina aðgerð; inntakssnið beggja gerða aðgerða má sjá í verkefnalýsingunni.

Tryggt er að summa $n$ yfir öll prófunartilvik fari ekki yfir $10^6$, summa $q$ yfir öll prófunartilvik fari ekki yfir $2\times 10^4$, og að í hverju prófunartilviki sé að minnsta kosti ein aðgerð af gerð 2.

Úttak

Fyrir hverja aðgerð af gerð 2 skal prenta fjölda þríhyrningsbila innan $[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