Problem G
Overloaded Ants

There are $n$ ants ordered in a row (from $1$ to $n$) that are on the way home. Initially, they do not have any thing to carry. Each ant $i$ has a capacity $w_ i$, $1\leq i \leq n$. If the ant $i$ carries more than $w_ i$, $1\leq i\leq n$, we said that it is overloaded. They can execute two type of operations.

• First, they can do rotate operation $1\ l\ r\ x$. The rotate operation $1\ l\ r\ x$ commands ants from position $l$ to $r$ to rotate from right to left $x$ times. For example, we have 5 ants: A B C D E in that order. If they get 1 2 5 2 order then the ants B, C, D, E have to perform two consecutive rotations to reorder their positions. After the first rotation, the order of all 5 ants is A C D E B. Then, the order becomes A D E B C after the second rotation. Note that the weight they carry do not change after executing this operation.

• Occasionally, they will meet a load of food and try to carry them by carry operation. In order to distribute their workloads, the carry operation $2\ l\ r\ x\ y$ commands each ant $i$ from position $l$ to $r$ to take an addition of $x+(i-l)\times y$ weight if it is not overloaded yet. After this operation, they want to know how many new ants are overloaded.

Given the sequence of the executed operation, your task is to compute the number of new overloaded ants after executing each carry operation.

Input

The first line is $n$, $m$ ($1 \leq n,m \leq 10^5$). The second line contains $n$ integer numbers of $w_ i$ ($1 \leq w_ i \leq 10^9$, $1\leq i \leq n$) that are the ants capacities. Each of the next $m$ lines contains either:

• $1\ l\ r\ x$ ($1 \leq l, r \leq n, 0 \leq x \leq 10^9$), if need to execute a rotate operation, or

• $2\ l\ r\ x\ y$ ($1 \leq l, r \leq n, 0 \leq x, y \leq 10^9$), if need to execute a carry operation.

Output

For each carry operation, print the number of new overloaded ants.

Sample Clarification

In the sample below, first, we have 5 ants: A B C D E with their capacity 4, 5, 1, 2, 3, respectively.

Their loads after the first operation: $l_ A=0, l_ B=1, l_ C=2, l_ D=0, l_ E=0$. Ant C is overloaded ($w_ C = 1 < l_ C=2$).

After the second operation, the new order is A D E B C.

After the third operation, we have $l_ A = 0, l_ D=0, l_ E=1, l_ B= 4, l_ C=2$. There is no new overloaded ant.

After the fourth operation, the new order is E B A D C.

After the fifth operation, we have $l_ E = 2, l_ B = 7, l_ A = 5, l_ D = 7, l_ C=2$. Ants A, B, D are overloaded.

5 5
4 5 1 2 3 
2 2 3 1 1
1 2 5 2 
2 3 5 1 2
1 1 4 2 
2 1 5 1 2

1 
0
3