E. Rikka with Data Structures
time limit per test
10 s
memory limit per test
1024 megabytes
input
standard input
output
standard output

As we know, Rikka is poor at data structures. Yuta is worrying about this situation, so he gives Rikka some tasks about data structures to practice. Here is one of them:

Yuta has an array $$$A$$$ with $$$n$$$ numbers, denoted by $$$A[1], A[2], \cdots, A[n]$$$. Then he makes $$$m$$$ operations on it.

There are three types of operations:

  • 1 l r k: for each index $$$i$$$ in $$$[l, r]$$$, change the value of $$$A[i]$$$ into $$$(A[i] + k)$$$;
  • 2 l r k: for each index $$$i$$$ in $$$[l, r]$$$, change the value of $$$A[i]$$$ into $$$k$$$;
  • 3 l r x: Yuta wants Rikka to count the number of different indices $$$y$$$ with $$$l \le y \le r$$$ such that $$$\max\{A[\min\{x, y\}], A[\min\{x, y\}+1], \cdots, A[\max\{x, y\}]\} = \max\{A[x], A[y]\}$$$.

It is too difficult for Rikka. Can you help her?

Input

The input contains several test cases, and the first line contains a single integer $$$T$$$ ($$$1 \le T \le 200$$$), the number of test cases.

For each test case, the first line contains two integers $$$n$$$ ($$$1 \le n \le 10^5$$$) and $$$m$$$ ($$$1 \le m \le 10^5$$$).

The second line contains $$$n$$$ integers $$$A[1], A[2], \cdots, A[n]$$$ ($$$1 \le A[i] \le 10^9$$$).

Then $$$m$$$ lines follow, each line of which describes an operation, containing four integers as mentioned above, satisfying $$$1 \le l \le r \le n$$$, $$$1 \le k \le 10^9$$$ and $$$1 \le x \le n$$$.

The input guarantees that there are at most $$$10$$$ test cases with $$$n \gt 10^3$$$ or $$$m \gt 10^3$$$.

Output

For each query, an operation of type $$$3$$$, output a single line with a single integer, the answer to this query.

Example
Input
1
10 10
1 3 2 5 2 3 1 6 4 5
3 5 7 8
3 5 7 4
1 1 5 2
3 1 10 4
3 1 10 8
2 8 8 8
3 1 10 8
3 1 10 4
2 4 8 1
3 1 2 10
Output
3
3
10
7
10
8
2