길이가 $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$)가 주어진다.

각 테스트 케이스에 대하여:

• 첫 번째 줄에 두 정수 $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