È dato un array $A=[a_1,a_2,\dots,a_n]$ di lunghezza $n$.
Per un intervallo $[x,y]$ ($1\le x\le y\le n$), se è possibile scegliere tre indici a due a due distinti $i,j,k\ (x\leq i\lt j\lt k\leq y)$ tra gli indici $x,x+1,\dots,y$ in modo che i valori corrispondenti possano costituire le lunghezze dei tre lati di un triangolo, ovvero $a_i+a_j\gt a_k, a_i+a_k\gt a_j, a_j+a_k\gt a_i$, allora $[x,y]$ è detto un intervallo triangolare. In particolare, un intervallo di lunghezza inferiore a $3$ non è mai un intervallo triangolare.
Ora è necessario supportare $q$ operazioni, ciascuna delle quali appartiene a uno dei due tipi seguenti:
- Operazione di primo tipo: $1\ p\ v\ (1\leq p\leq n, 1\leq v\leq 10^{18})$, modifica $a_p$ in $v$.
- Operazione di secondo tipo: $2\ l\ r\ (1\leq l\leq r\leq n)$, chiede quanti tra tutti gli intervalli $[x,y]$ che soddisfano $l\le x\le y\le r$ siano intervalli triangolari.
Per ogni operazione di secondo tipo, stampa il risultato corrispondente.
Input
Ogni test contiene più casi di prova. La prima riga contiene il numero di casi di prova $T$ ($1\le T\le 10^4$).
Per ogni caso di prova:
- La prima riga contiene due interi $n$, $q$ ($1\leq n\leq 10^6,~1\leq q\leq 2\times 10^4$), che rappresentano la lunghezza della sequenza $A$ e il numero di interrogazioni.
- La seconda riga contiene $n$ interi $a_1,a_2,\ldots,a_n$ ($1\le a_i\le 10^{18}$), che rappresentano gli elementi della sequenza data $A$.
- Le successive $q$ righe contengono ciascuna $3$ interi che rappresentano un'operazione; il formato di input dei due tipi di operazioni è descritto nel testo del problema.
È garantito che la somma di $n$ su tutti i casi di prova non superi $10^6$, la somma di $q$ su tutti i casi di prova non superi $2\times 10^4$, e che ogni caso di prova contenga almeno un'operazione di secondo tipo.
Output
Per ogni operazione di secondo tipo, stampa il numero di intervalli triangolari all'interno di $[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