이멜다의 구두 쇼핑

구두 전문점 와리왑은 세계에서 가장 이름난 구두 가게다. 이 가게는 매일 최고급 구두 $N$켤레를 전시한다. 구두 한 켤레마다 받침대를 하나씩 두고, 그 받침대를 일렬로 늘어놓는 방식이다. 받침대에는 왼쪽부터 차례로 $1$번부터 $N$번까지 번호를 매긴다.

가게 문을 여는 시각에 $i$번 받침대에 놓인 구두의 가격은 $p_i$ 페소다. 영업 중에 매니저는 가격을 올리기도 하고, 덜 주목받는 구두를 더 보여 주려고 진열 순서를 바꾸기도 한다. 매니저는 하루 중 언제든지 받침대 구간

$S_{i,j} = \{i, i+1, \dots, j-1, j\}$

을 고른 뒤 다음 둘 중 하나를 한다.

• INCREASE: 고른 받침대에 놓인 구두의 가격을 $k$ 페소씩 올린다. 가격은 받침대가 아니라 구두에 붙어 있다.
• REVERSE: 고른 받침대에 놓인 구두의 순서를 뒤집는다. $i$번 받침대에 있던 구두는 $j$번으로 옮겨지고, $i+1$번에 있던 구두는 $j-1$번으로 옮겨지며, 나머지도 같은 방식으로 옮겨진다.

오늘은 와리왑의 단골손님 이멜다의 생일이다. 이멜다 마음대로라면 $N$켤레를 전부 사겠지만, 남편 마샬이 빚이 많다고 말렸고 부부는 살 구두를 정하는 규칙에 합의했다.

규칙은 이렇다. 이멜다가 $a \le b$인 정수 $a$와 $b$를 고르면, $a$번부터 $b$번까지의 받침대에 지금 놓여 있는 구두가 이멜다가 고른 구두가 된다. 여기에 마샬이 조건을 하나 덧붙였고, 부부는 이 조건을 마샬의 법이라고 부른다. 마샬의 법은 이멜다가 고른 구두를 왼쪽에서 오른쪽으로 보았을 때 가격이 계속 커져야 한다고 정한다. 즉 $m < n$이면 $n$번 받침대의 구두가 $m$번 받침대의 구두보다 비싸야 한다. 고른 구두가 마샬의 법을 어기면 부부는 아무것도 사지 않고 집으로 돌아가고, 마샬은 다시는 와리왑에 오지 않겠다고 선언한다.

이런 조건에도 이멜다는 생일 쇼핑이 기대된다. 이멜다는 매니저가 무언가를 바꿀 때마다, 마샬의 법을 지키면서 쇼핑백을 채우는 방법이 몇 가지인지 알고 싶다. 생일에 빈손으로 돌아갈 생각은 없으므로 적어도 한 켤레는 산다. 예를 들어 구두가 $N = 5$켤레이고 가격이 다음과 같다고 하자.

이멜다의 쇼핑백에 담길 수 있는 구두는 다음과 같다.

• 쇼핑백에 정확히 한 켤레가 담기는 경우는 다섯 가지다. $a = b$로 고르면 되고, 그런 경우가 다섯 가지 있다.
• 쇼핑백에 정확히 두 켤레가 담기는 경우는 두 가지다. $a = 3, b = 4$(구두 C와 D)로 고르거나 $a = 4, b = 5$(구두 D와 E)로 고르면 된다.
• 쇼핑백에 정확히 세 켤레가 담기는 경우는 한 가지다. $a = 3, b = 5$(구두 C, D, E)로 고르는 경우다.

나머지 조합은 모두 마샬의 법을 어긴다는 사실을 보일 수 있다. 따라서 경우의 수는 $8$가지다.

이멜다의 충직한 하인인 당신이 하루 중 어느 시점에서든 이멜다의 질문에 답해야 한다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 구두의 수 $N$과 매니저가 하는 변경의 수 $Q$가 공백을 사이에 두고 주어진다. 다음 줄에는 구두의 초기 가격 $p_1, p_2, \dots, p_N$이 공백을 사이에 두고 주어진다.

이어지는 $Q$개의 줄에는 매니저가 하는 변경이 시간 순서대로 한 줄에 하나씩 주어진다. 각 줄은 다음 두 형식 중 하나다.

• INC i j k: 문제에서 설명한 INCREASE 연산이다.
• REV i j: 문제에서 설명한 REVERSE 연산이다.

제한

• $1 \le T \le 2$
• $1 \le N \le 10^5$
• $1 \le Q \le 10^5$
• $1 \le i \le j \le N$
• $1 \le k \le 10^9$
• $1 \le p_i \le 10^9$

매니저가 가격이나 순서를 바꿀 때마다 정수 $X$를 한 줄에 하나씩 출력한다. $X$는 그 변경이 끝난 직후에 이멜다가 마샬의 법을 지키면서 쇼핑백을 채우는 방법의 수다.