俾定一個長度為 $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