View Russian Translation

Mary is about to get married! She has already bought an extremely beautiful wedding dress, a wonderful chapel has also been reserved as well as her guests have been invited. There's only one thing left undone: Mary still doesn't have a groom!

There are n potential grooms standing in a straight line. The grooms are numbered 1 through n, each groom has an integer \(A_i\) assigned to him, denoting the level of his attractiveness. If \(A_i \ge A_j\), then the i'th candidate is said to be no less attractive, than the j'th candidate. You may assume, that any of the candidates is more than happy to marry the bride, so the marriage is only a question of her will.

Mary has decided, that she would make several runs in order to find a perfect future husband. Each of the runs is described by two integers l and r. If \(l \le r\), then Mary considers the candidates with indices \(l, l + 1, ..., r - 1, r\) one by one, otherwise she considers the same candidates, but in the reversed order (\(r, r - 1, ..., l + 1, l\)). While considering them in the corresponding order, Mary gets extremely excited each time she sees a candidate, which is no less attractive than any of the candidates before him in this run. According to the process, Mary always gets excited when she sees the first candidate in a run.

For example, if \(A = [2, 1, 3, 2, 3]\), \(l = 1\) and \(r = 5\), then Mary will get excited when she will see candidates with indices \(1, 3\) and 5. If \(r = 5\) and \(l = 1\), then she will get excited only when she will see candidates with indices 5 and 3.

For each of the runs, Mary would like to know the number of times she will get excited during this run. But the candidates are not static, they may become more attractive (or less attractive) in the meantime: sometimes, Mary receives information, that all the candidates with indices from l to r have increased their levels of attractiveness by some integer x.

There are so many candidates! The wedding is soon, Mary definitely won't be able to do all the runs by her own! Your task is to help Mary with managing her runs.

Input format

The first line of the input contains one integer t denoting the number of test cases.

The first line of the test case description contains two integers n and q, the latter denotes the number of queries to process.

The second line of the test case description contains n integers denoting \(A_1, A_2, ..., A_n\).

Each of the next q lines contains the description for the corresponding query in one of the following formats:

\(\text{1 l r}\): make an \((l, r)\)-run and find the number of times Mary will get excited during this run
\(\text{2 l r x}\): increase the level of attractiveness for all the candidates with indices from l to r by x

Output format

For each of the queries of the first type, output the required integer on a separate line.

Constraints

\(1 \le t \le 5\)
\(1 \le n \le 250{,}000\)
\(0 \le q \le 100{,}000\)
\(|A_i| \le 10^9\) for each candidate
\(1 \le l, r \le n\) for each query of the first type
\(1\le l \le r \le n\), \(|x| \le 10^9\) for each query of the second type

Subtasks

Extra constraints	Points	Which tests
\(n \le 2500, q \le 1000\)	25	1
no queries of the second type	25	2
no extra constraints	50	3