Description

{{The leader has recently learned a magical spell that can make people taller. He plans to demonstrate it to every hero in the XMYZ Information Group. Thus, $N$ heroes gather once again, lining up in a row and being numbered $1, 2, \ldots, N$.

Each person’s height is initially a positive integer not exceeding $1000$. Each time the leader casts the spell, he can add an integer $W$ to the heights of all heroes in the closed interval $[L, R]$ ($1≤L≤R≤N$). (Although $L=R$ is not standard interval notation, we can regard it as increasing only the height of the $L$-th hero.)

CYZ, Guang Ge, and ZJQ do not believe in the leader’s magic, so they sometimes ask WD how many heroes in the closed interval $[L, R]$ have height greater than or equal to $C$, to verify whether the magic really works.

WD is extremely lazy, so he hands this task over to you.}}

Input Format

{{The first line contains two integers $N, Q$. $Q$ is the total number of queries and spells.

The second line contains $N$ positive integers; the $i$-th number is the height of the $i$-th hero.

Lines $3$ through $Q+2$ each contain one operation:

1. If the first letter is M, then three numbers $L, R, W$ follow. Add $W$ to the heights of all heroes in the closed interval $[L, R]$.

2. If the first letter is A, then three numbers $L, R, C$ follow. Query how many heroes in the closed interval $[L, R]$ have height greater than or equal to $C$.}}

Output Format

{{For each A query, output one line containing a single integer: the number of heroes with height greater than or equal to $C$ in $[L, R]$.}}

5 3
1 2 3 4 5
A 1 5 4
M 3 5 1
A 1 5 4

2
3

Hint

{{Sample explanation:

Originally, the $5$ heroes’ heights are $1, 2, 3, 4, 5$, so there are $2$ heroes in $[1, 5]$ whose heights are at least $4$. After the leader casts the spell, the heights become $1, 2, 4, 5, 6$, so there are $3$ heroes in $[1, 5]$ whose heights are at least $4$.

Constraints:

• For $30\%$ of the testdata, $N≤1000$, $Q≤1000$.
• For $100\%$ of the testdata, $N≤10^6$, $Q≤3000$, $1≤W≤1000$, $1≤C≤10^9$.

$\text{upd 2022.8.18}$: A new set of Hack testdata has been added. $\text{upd 2023.8.16}$: A new set of Hack testdata has been added.}}

Translated by ChatGPT 5