给定一个长度为 $n$ 的数组 $A=[a_1,a_2,\dots,a_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)$ ，查询满足 $l\le x\le y\le r$ 的所有区间 $[x,y]$ 中，有多少个是三角形区间。

请对于每一个第二类操作，输出对应的统计结果。

输入格式

每个测试点包含多组测试用例。第一行包含测试用例的数量 $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