أُعطيت مصفوفة $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\ 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)$، الاستعلام عن عدد المجالات $[x,y]$ التي تحقق $l\le x\le y\le r$ وتكون مجالات مثلثية.

يرجى طباعة النتيجة الإحصائية المقابلة لكل عملية من النوع الثاني.

الإدخال

يحتوي كل اختبار على عدة حالات اختبار. يحتوي السطر الأول على عدد حالات الاختبار $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