Description

The newbie edt gives this problem to you—a master of data structures. Since this is the first problem, it is not that hard.

The problem is simplified as follows:

• Initially, every element in the array is $0$.
• You are given $\text{n}, \text{opt}, \text{mod}, \text{min}, \text{max}$ within the range of int.

Operations $A, Q$:

• A L R X means add $X$ to the interval $[L, R]$. (Every element from $L$ to $R$ in the array is increased by $X$.)
• Q L R asks, in the interval $[L, R]$, for the count of elements $T$ such that $\text{min} \le (T \times i \mod \text{mod}) \le \text{max}$, where $i$ is the array index. (The value of the element times its index, modulo $\text{mod}$, falls within the range from $\min$ to $\max$, inclusive.)

Because edt invited a non-3D hamster to help, some queries are postponed into a chaotic spacetime. The number of online Q operations will not exceed $1000$. Unfortunately, there may be many postponed queries (less than $1 \times 10^7$), but it is guaranteed that after these postponed queries, there will be no more update operations (that is, at the end there are many queries but no modifications).

Input Format

• The first line gives $\text{n}, \text{opt}, \text{mod}, \text{min}, \text{max}$, representing the sequence size, the number of operations, the modulo, the minimum value, and the maximum value.
• Then follow $\text{opt}$ lines, each being one of:
  • A L R X denotes a range add. $\text{X}$ is guaranteed to be within the range of int.
  • Q L R denotes a range query asking for the count that satisfies the condition.
• The $(\text{opt} + 1)$-th line gives a number $\text{Final}$, meaning there are $\text{Final}$ postponed queries after that.
• Then follow $\text{Final}$ lines, each giving $L, R$, asking for the count that satisfies the condition in $[L, R]$.

Output Format

• For each Q operation, output one number per line representing the answer to that query.
• Then output $\text{Final}$ lines, each with one number representing the answer to each postponed query.

3 2 4 0 2
A 1 3 5
Q 2 3 
5
1 3
2 3
1 1 
2 2 
3 3

1
2
1
1
1
0

17 25 4098 310 2622
A 10 16 657212040
A 4 15 229489140
A 1 2 -433239891
A 3 12 532385784
A 10 17 56266644
A 8 10 10038874
A 6 9 13084764
A 4 5 -9206340
Q 2 8
A 2 4 -43223955
A 6 9 31478706
A 2 4 189818310
A 2 8 179421180
A 2 8 40354938
Q 8 14
A 3 6 57229575
A 6 13 132795740
A 2 17 14558022
A 14 15 -552674185
A 5 11 -1104138
Q 2 12
Q 1 14
A 3 9 524902182
A 8 12 114291440
A 3 7 107531442
1
11 12

3
6
7
8
2

20 3 4317 1020 2232
A 8 15 -434078222
A 1 2 54988154
A 13 19 81757858
15
7 11
3 5
3 9
6 9
9 13
6 19
1 20
3 5
3 10
1 7
2 14
6 10
2 3
2 3
10 12

0
0
0
0
0
2
2
0
0
0
0
0
0
0
0

Hint

Sample Explanation

Explanation for Sample 1:

In Sample 1, the array $a$ becomes $5, 5, 5$. Each $a_i \times i \mod 4$ equals $1, 2, 3$.

For the $\text{Final}$ queries, in $[1, 3]$, the count of values greater than or equal to $0$ and less than or equal to $2$ is $2$.

The rest are similar.

Notes

• Important:
  • Regarding modulo with negative numbers, follow C++ truncation toward $0$. For example: [ $-7 \bmod 3 = -1$ ] [ $7 \bmod 3 = 1$ ].
• There are 50 test points, each worth 2 points. Because there are many test points, please do not intentionally submit many times to jam the judge. The author edt expresses sincere thanks.

Constraints

If you cannot solve all points, try to obtain partial scores. All testdata are randomly generated.

Translated by ChatGPT 5