Задано масив $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]$.

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