Ұзындығы $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$) берілген.

Әрбір тест жағдайы үшін:

• Бірінші жолда $A$ тізбегінің ұзындығын және сұраныстар санын білдіретін екі бүтін сан $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}$) берілген.
• Келесі $q$ жолдың әрқайсысында бір операцияны білдіретін $3$ бүтін сан берілген; екі түрдегі операциялардың енгізу форматы есептің шартында көрсетілген.

Барлық тест жағдайлары бойынша $n$ қосындысы $10^6$-нен аспайтынына, барлық тест жағдайлары бойынша $q$ қосындысы $2\times 10^4$-нен аспайтынына және әрбір тест жағдайында кемінде бір екінші түрдегі операция болатынына кепілдік беріледі.

Шығару деректері

Әрбір екінші түрдегі операция үшін $[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