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