נתון מערך $A=[a_1,a_2,\dots,a_n]$ באורך $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)$, שואלת כמה מבין כל הקטעים $[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]$.

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