Imelda's Shopping Spree

Shoe Wariwap is the most famous shoe boutique in the world. Every day the shop displays $N$ of the finest pairs of shoes ever made. Each pair stands on its own pedestal, and the pedestals are arranged in a row. The pedestals are numbered from $1$ to $N$, where pedestal $1$ is the leftmost one.

When Shoe Wariwap opens, the pair on pedestal $i$ is worth $p_i$ pesos. During the day the manager may raise prices or shuffle the display order so that the less appreciated pairs get more attention. At any moment the manager picks a set of pedestals

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

and does one of the following.

• INCREASE the price of the shoes standing on the chosen pedestals. The shoes on pedestals $i$ through $j$ each become $k$ pesos more expensive. The price belongs to the shoes, not to the pedestal.
• REVERSE the order of the shoes on the chosen pedestals. The pair that was on pedestal $i$ moves to pedestal $j$, the pair that was on pedestal $i+1$ moves to pedestal $j-1$, and so on.

Today is the birthday of one of Shoe Wariwap's best customers, Imelda. If it were up to her, she would buy all $N$ pairs. Her husband Marshall tells her they are deep in debt, so the two agree on a system that decides which pairs she buys.

The system works like this. Imelda picks two integers $a$ and $b$ with $a \le b$. Her chosen shoes are the ones that currently stand on pedestals $a$ through $b$. Marshall adds one more condition, which the couple fondly calls Marshall's Law. Marshall's Law says that Imelda's chosen shoes, read from left to right, must increase in price. That is, if $m < n$, then the pair on pedestal $n$ must be more expensive than the pair on pedestal $m$. If the chosen shoes break Marshall's Law, the couple goes home with nothing and Marshall vows never to return to Shoe Wariwap.

Imelda is still excited about her big shopping day. Every time the manager changes something, she wants to know how many ways she can fill her shopping bag while obeying Marshall's Law. She would never go home empty handed on her birthday, so she buys at least one pair. For example, consider $N = 5$ pairs with the following prices.

Here is everything Imelda's shopping bag might contain.

• There are five ways for the bag to hold exactly one pair. Imelda chooses $a = b$, and there are five such choices.
• There are two ways for the bag to hold exactly two pairs. She can choose $a = 3, b = 4$ (shoes C and D) or $a = 4, b = 5$ (shoes D and E).
• There is one way for the bag to hold exactly three pairs. She chooses $a = 3, b = 5$ (shoes C, D and E).

Every other combination breaks Marshall's Law, so there are $8$ possibilities in total.

You are her loyal servant, and you must answer her question at any point during the day.

The first line contains a single integer $T$, the number of test cases.

The first line of each test case contains two space separated integers $N$, the number of pairs of shoes, and $Q$, the number of changes the manager makes. The next line contains $N$ space separated integers $p_1, p_2, \dots, p_N$, the initial prices.

The next $Q$ lines describe the changes in chronological order, one per line. Each line has one of the following formats.

• INC i j k describes an INCREASE operation as explained in the statement.
• REV i j describes a REVERSE operation as explained in the statement.

Constraints

• $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$

Every time the manager makes a change, whether to a price or to the order, print a line with a single integer $X$. $X$ is the number of ways Imelda can fill her shopping bag right after that change while obeying Marshall's Law.