長さ $n$ の配列 $A=[a_1,a_2,\dots,a_n]$ が与えられます。

区間 $[x,y]$（$1\le x\le y\le n$）について、添字 $x,x+1,\dots,y$ の中から相異なる3つの添字 $i,j,k\ (x\leq i\lt j\lt k\leq y)$ を選んで、対応する値が三角形の3辺の長さとなり得る、すなわち $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$ 回の操作を処理してください。各操作は以下の2種類のいずれかです：

• 第1種操作：$1\ p\ v\ (1\leq p\leq n, 1\leq v\leq 10^{18})$ — $a_p$ を $v$ に変更する。
• 第2種操作：$2\ l\ r\ (1\leq l\leq r\leq n)$ — $l\le x\le y\le r$ を満たすすべての区間 $[x,y]$ のうち、三角形区間であるものの個数を求める。

各第2種操作に対して、対応する集計結果を出力してください。

入力

各テストファイルには複数のテストケースが含まれます。最初の行にはテストケースの個数 $T$（$1\le T\le 10^4$）が与えられます。

各テストケースについて：

• 1行目には2つの整数 $n$, $q$（$1\leq n\leq 10^6,~1\leq q\leq 2\times 10^4$）が与えられ、数列 $A$ の長さと操作の回数を表します。
• 2行目には $n$ 個の整数 $a_1,a_2,\ldots,a_n$（$1\le a_i\le 10^{18}$）が与えられ、数列 $A$ の各要素を表します。
• 続く $q$ 行にはそれぞれ $3$ 個の整数が与えられ、1回の操作を表します。2種類の操作の入力形式は問題文の通りです。

すべてのテストケースにおける $n$ の総和は $10^6$ 以下、すべてのテストケースにおける $q$ の総和は $2\times 10^4$ 以下であり、各テストケースに少なくとも1回の第2種操作が含まれることが保証されます。

出力

各第2種操作について、$[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