Diberikan sebuah array $A=[a_1,a_2,\dots,a_n]$ dengan panjang $n$.

Untuk sebuah interval $[x,y]$ ($1\le x\le y\le n$), jika kita dapat memilih tiga indeks yang saling berbeda $i,j,k\ (x\leq i\lt j\lt k\leq y)$ dari indeks $x,x+1,\dots,y$ sehingga nilai-nilai yang bersesuaian dapat membentuk panjang ketiga sisi sebuah segitiga, yaitu $a_i+a_j\gt a_k, a_i+a_k\gt a_j, a_j+a_k\gt a_i$, maka $[x,y]$ disebut interval segitiga. Secara khusus, interval dengan panjang kurang dari $3$ tidak pernah merupakan interval segitiga.

Sekarang Anda perlu mendukung $q$ operasi, di mana setiap operasi adalah salah satu dari dua jenis berikut:

• Operasi jenis pertama: $1\ p\ v\ (1\leq p\leq n, 1\leq v\leq 10^{18})$, mengubah $a_p$ menjadi $v$.
• Operasi jenis kedua: $2\ l\ r\ (1\leq l\leq r\leq n)$, menanyakan berapa banyak interval $[x,y]$ yang memenuhi $l\le x\le y\le r$ yang merupakan interval segitiga.

Untuk setiap operasi jenis kedua, keluarkan hasil perhitungan yang sesuai.

Masukan

Setiap pengujian berisi beberapa kasus uji. Baris pertama berisi jumlah kasus uji $T$ ($1\le T\le 10^4$).

Untuk setiap kasus uji:

• Baris pertama berisi dua bilangan bulat $n$, $q$ ($1\leq n\leq 10^6,~1\leq q\leq 2\times 10^4$), yang menyatakan panjang barisan $A$ dan jumlah kueri.
• Baris kedua berisi $n$ bilangan bulat $a_1,a_2,\ldots,a_n$ ($1\le a_i\le 10^{18}$), yang menyatakan elemen-elemen dari barisan $A$ yang diberikan.
• $q$ baris berikutnya masing-masing berisi $3$ bilangan bulat yang menyatakan satu operasi. Format masukan untuk kedua jenis operasi dapat dilihat pada deskripsi soal.

Dijamin bahwa jumlah $n$ di semua kasus uji tidak melebihi $10^6$, jumlah $q$ di semua kasus uji tidak melebihi $2\times 10^4$, dan setiap kasus uji memiliki setidaknya satu operasi jenis kedua.

Keluaran

Untuk setiap operasi jenis kedua, keluarkan jumlah interval segitiga di dalam $[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