You are given an array $A=[a_1,a_2,\dots,a_n]$ of length $n$.

For an interval $[x,y]$ ($1\le x\le y\le n$), if we can choose three pairwise distinct indices $i,j,k\ (x\leq i\lt j\lt k\leq y)$ from the indices $x,x+1,\dots,y$ such that their corresponding values can form the lengths of the three sides of a triangle, namely $a_i+a_j\gt a_k, a_i+a_k\gt a_j, a_j+a_k\gt a_i$, then $[x,y]$ is called a triangle interval. In particular, an interval of length less than $3$ is never a triangle interval.

Now you need to support $q$ operations, where each operation is one of the following two types:

• Type 1 operation: $1\ p\ v\ (1\leq p\leq n, 1\leq v\leq 10^{18})$, which modifies $a_p$ to $v$.
• Type 2 operation: $2\ l\ r\ (1\leq l\leq r\leq n)$, which queries how many intervals $[x,y]$ satisfying $l\le x\le y\le r$ are triangle intervals.

Please output the corresponding count for each Type 2 operation.

Input

Each test contains multiple test cases. The first line contains the number of test cases $T$ ($1\le T\le 10^4$).

For each test case:

• The first line contains two integers $n$, $q$ ($1\leq n\leq 10^6,~1\leq q\leq 2\times 10^4$), representing the length of sequence $A$ and the number of operations.
• The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1\le a_i\le 10^{18}$), representing the elements of the given sequence $A$.
• The next $q$ lines each contain $3$ integers representing an operation. The input format of the two types of operations can be found in the problem description.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$, the sum of $q$ over all test cases does not exceed $2\times 10^4$, and each test case has at least one Type 2 operation.

Output

For each Type 2 operation, output the number of triangle intervals within $[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