Annetaan pituutta $n$ oleva taulukko $A=[a_1,a_2,\dots,a_n]$.

Jos välille $[x,y]$ ($1\le x\le y\le n$) voidaan valita indeksien $x,x+1,\dots,y$ joukosta kolme pareittain eri indeksiä $i,j,k\ (x\leq i\lt j\lt k\leq y)$ siten, että niitä vastaavat arvot voivat muodostaa kolmion kolmen sivun pituudet, eli $a_i+a_j\gt a_k, a_i+a_k\gt a_j, a_j+a_k\gt a_i$, niin väliä $[x,y]$ kutsutaan kolmioväliksi. Erityisesti väli, jonka pituus on alle $3$, ei ole koskaan kolmioväli.

Nyt tulee tukea $q$ operaatiota, joista jokainen on jompikumpi seuraavista kahdesta tyypistä:

• Tyypin 1 operaatio: $1\ p\ v\ (1\leq p\leq n, 1\leq v\leq 10^{18})$, muuttaa alkion $a_p$ arvoksi $v$.
• Tyypin 2 operaatio: $2\ l\ r\ (1\leq l\leq r\leq n)$, kysyy, kuinka moni kaikista ehdon $l\le x\le y\le r$ täyttävistä väleistä $[x,y]$ on kolmiovälejä.

Tulosta jokaiselle tyypin 2 operaatiolle vastaava lukumäärä.

Syöte

Jokainen testi sisältää useita testitapauksia. Ensimmäinen rivi sisältää testitapausten lukumäärän $T$ ($1\le T\le 10^4$).

Jokaiselle testitapaukselle:

• Ensimmäinen rivi sisältää kaksi kokonaislukua $n$, $q$ ($1\leq n\leq 10^6,~1\leq q\leq 2\times 10^4$), jotka ilmaisevat jonon $A$ pituuden ja kyselyiden lukumäärän.
• Toinen rivi sisältää $n$ kokonaislukua $a_1,a_2,\ldots,a_n$ ($1\le a_i\le 10^{18}$), jotka ilmaisevat annetun jonon $A$ alkiot.
• Seuraavat $q$ riviä sisältävät kukin $3$ kokonaislukua, jotka kuvaavat yhden operaation; molempien operaatiotyyppien syötemuoto on esitetty tehtävänannossa.

On taattu, että lukujen $n$ summa yli kaikkien testitapausten on enintään $10^6$, lukujen $q$ summa yli kaikkien testitapausten on enintään $2\times 10^4$ ja jokaisessa testitapauksessa on vähintään yksi tyypin 2 operaatio.

Tuloste

Tulosta jokaiselle tyypin 2 operaatiolle kolmiovälien lukumäärä välillä $[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