Dana jest tablica $A=[a_1,a_2,\dots,a_n]$ o długości $n$.

Dla przedziału $[x,y]$ ($1\le x\le y\le n$), jeśli spośród indeksów $x,x+1,\dots,y$ można wybrać trzy parami różne indeksy $i,j,k\ (x\leq i\lt j\lt k\leq y)$ takie, że odpowiadające im wartości mogą tworzyć długości trzech boków trójkąta, to znaczy $a_i+a_j\gt a_k, a_i+a_k\gt a_j, a_j+a_k\gt a_i$, to przedział $[x,y]$ nazywamy przedziałem trójkątnym. W szczególności przedział o długości mniejszej niż $3$ nigdy nie jest przedziałem trójkątnym.

Należy obsłużyć $q$ operacji, z których każda jest jednego z dwóch poniższych typów:

• Operacja pierwszego typu: $1\ p\ v\ (1\leq p\leq n, 1\leq v\leq 10^{18})$, zmienia wartość $a_p$ na $v$.
• Operacja drugiego typu: $2\ l\ r\ (1\leq l\leq r\leq n)$, pyta, ile spośród wszystkich przedziałów $[x,y]$ spełniających $l\le x\le y\le r$ jest przedziałami trójkątnymi.

Dla każdej operacji drugiego typu wypisz odpowiedni wynik.

Wejście

Każdy test zawiera wiele przypadków testowych. Pierwszy wiersz zawiera liczbę przypadków testowych $T$ ($1\le T\le 10^4$).

Dla każdego przypadku testowego:

• Pierwszy wiersz zawiera dwie liczby całkowite $n$, $q$ ($1\leq n\leq 10^6,~1\leq q\leq 2\times 10^4$), oznaczające długość ciągu $A$ oraz liczbę zapytań.
• Drugi wiersz zawiera $n$ liczb całkowitych $a_1,a_2,\ldots,a_n$ ($1\le a_i\le 10^{18}$), oznaczających kolejne elementy danego ciągu $A$.
• Kolejne $q$ wierszy zawiera po $3$ liczby całkowite oznaczające jedną operację; format wejścia dla obu typów operacji opisano w treści zadania.

Gwarantuje się, że suma $n$ po wszystkich przypadkach testowych nie przekracza $10^6$, suma $q$ po wszystkich przypadkach testowych nie przekracza $2\times 10^4$ oraz w każdym przypadku testowym występuje co najmniej jedna operacja drugiego typu.

Wyjście

Dla każdej operacji drugiego typu wypisz liczbę przedziałów trójkątnych wewnątrz $[l,r]$.

Przykład

Wejście 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

Wyjście 1

1
0
1
7
1