Cho một mảng $A=[a_1,a_2,\dots,a_n]$ có độ dài $n$.

Đối với một đoạn $[x,y]$ ($1\le x\le y\le n$), nếu có thể chọn ra ba chỉ số đôi một khác nhau $i,j,k\ (x\leq i\lt j\lt k\leq y)$ từ các chỉ số $x,x+1,\dots,y$ sao cho các giá trị tương ứng của chúng có thể làm độ dài ba cạnh của một tam giác, tức là $a_i+a_j\gt a_k, a_i+a_k\gt a_j, a_j+a_k\gt a_i$, thì $[x,y]$ được gọi là một đoạn tam giác. Đặc biệt, các đoạn có độ dài nhỏ hơn $3$ không bao giờ là đoạn tam giác.

Bây giờ bạn cần hỗ trợ $q$ thao tác, mỗi thao tác thuộc một trong hai loại sau:

• Thao tác loại 1: $1\ p\ v\ (1\leq p\leq n, 1\leq v\leq 10^{18})$, thay đổi $a_p$ thành $v$.
• Thao tác loại 2: $2\ l\ r\ (1\leq l\leq r\leq n)$, truy vấn xem trong tất cả các đoạn $[x,y]$ thỏa mãn $l\le x\le y\le r$, có bao nhiêu đoạn là đoạn tam giác.

Hãy in ra kết quả thống kê tương ứng cho mỗi thao tác loại 2.

Dữ liệu vào

Mỗi test chứa nhiều bộ dữ liệu. Dòng đầu tiên chứa số lượng bộ dữ liệu $T$ ($1\le T\le 10^4$).

Đối với mỗi bộ dữ liệu:

• Dòng đầu tiên chứa hai số nguyên $n$, $q$ ($1\leq n\leq 10^6,~1\leq q\leq 2\times 10^4$), biểu thị độ dài của dãy $A$ và số lượng truy vấn.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\ldots,a_n$ ($1\le a_i\le 10^{18}$), biểu thị các phần tử của dãy $A$ đã cho.
• $q$ dòng tiếp theo, mỗi dòng chứa $3$ số nguyên biểu thị một thao tác; định dạng đầu vào của hai loại thao tác có thể xem trong phần mô tả bài toán.

Đảm bảo tổng của $n$ trên tất cả các bộ dữ liệu không vượt quá $10^6$, tổng của $q$ trên tất cả các bộ dữ liệu không vượt quá $2\times 10^4$, và mỗi bộ dữ liệu có ít nhất một thao tác loại 2.

Dữ liệu ra

Đối với mỗi thao tác loại 2, in ra số lượng đoạn tam giác nằm trong $[l,r]$.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

1
0
1
7
1