Дан массив $A=[a_1,a_2,\dots,a_n]$ длины $n$.

Для отрезка $[x,y]$ ($1\le x\le y\le n$), если среди индексов $x,x+1,\dots,y$ можно выбрать три попарно различных индекса $i,j,k\ (x\leq i\lt j\lt k\leq y)$ так, что соответствующие им значения могут быть длинами трёх сторон треугольника, то есть $a_i+a_j\gt a_k, a_i+a_k\gt a_j, a_j+a_k\gt a_i$, то отрезок $[x,y]$ называется треугольным отрезком. В частности, отрезок длины меньше $3$ никогда не является треугольным отрезком.

Требуется поддерживать $q$ операций, каждая из которых относится к одному из двух следующих типов:

• Операция первого типа: $1\ p\ v\ (1\leq p\leq n, 1\leq v\leq 10^{18})$, изменить $a_p$ на $v$.
• Операция второго типа: $2\ l\ r\ (1\leq l\leq r\leq n)$, узнать, сколько среди всех отрезков $[x,y]$, удовлетворяющих условию $l\le x\le y\le r$, являются треугольными отрезками.

Для каждой операции второго типа выведите соответствующий результат.

Входные данные

Каждый тест содержит несколько наборов входных данных. Первая строка содержит количество наборов входных данных $T$ ($1\le T\le 10^4$).

Для каждого набора входных данных:

• Первая строка содержит два целых числа $n$, $q$ ($1\leq n\leq 10^6,~1\leq q\leq 2\times 10^4$), обозначающих длину последовательности $A$ и количество запросов.
• Вторая строка содержит $n$ целых чисел $a_1,a_2,\ldots,a_n$ ($1\le a_i\le 10^{18}$), обозначающих элементы заданной последовательности $A$.
• Следующие $q$ строк содержат по $3$ целых числа, описывающих одну операцию; формат входных данных для обоих типов операций описан в условии задачи.

Гарантируется, что сумма $n$ по всем наборам входных данных не превосходит $10^6$, сумма $q$ по всем наборам входных данных не превосходит $2\times 10^4$, и в каждом наборе входных данных есть хотя бы одна операция второго типа.

Выходные данные

Для каждой операции второго типа выведите количество треугольных отрезков внутри $[l,r]$.

Примеры

Входные данные 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

Выходные данные 1

1
0
1
7
1