กำหนดอาร์เรย์ $A=[a_1,a_2,\dots,a_n]$ ที่มีความยาว $n$

สำหรับช่วง $[x,y]$ ($1\le x\le y\le n$) หากสามารถเลือกดัชนีที่แตกต่างกันสามตัว $i,j,k\ (x\leq i\lt j\lt k\leq y)$ จากดัชนี $x,x+1,\dots,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: $1\ p\ v\ (1\leq p\leq n, 1\leq v\leq 10^{18})$ เปลี่ยนค่า $a_p$ เป็น $v$
• การดำเนินการประเภทที่ 2: $2\ l\ r\ (1\leq l\leq r\leq n)$ สอบถามว่าในบรรดาช่วง $[x,y]$ ทั้งหมดที่สอดคล้องกับ $l\le x\le y\le r$ มีกี่ช่วงที่เป็นช่วงสามเหลี่ยม

โปรดแสดงผลลัพธ์การนับที่สอดคล้องกันสำหรับการดำเนินการประเภทที่ 2 แต่ละครั้ง

ข้อมูลนำเข้า

แต่ละชุดทดสอบประกอบด้วยหลายกรณีทดสอบ บรรทัดแรกประกอบด้วยจำนวนกรณีทดสอบ $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$ และรับประกันว่าแต่ละกรณีทดสอบมีการดำเนินการประเภทที่ 2 อย่างน้อยหนึ่งครั้ง

ข้อมูลส่งออก

สำหรับการดำเนินการประเภทที่ 2 แต่ละครั้ง ให้แสดงจำนวนช่วงสามเหลี่ยมภายใน $[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