Background

Introduction

If you learn data structures well, your future job will have no worries.

Edgration (hereafter edt) is a "ju ruo" (newbie) who likes to mess with data structures. One day, he decided to make things hard for some "dalao" (experts):

edt: I want a data structure that supports range add and can return the number of elements greater than $k$ in a given interval.

dalao1: sb segment tree.

dalao2: sb block decomposition.

dalao3: sb balanced tree.

edt: Not good enough, then add modulo: count, after taking modulo, how many numbers in the interval are greater than MIN and less than MAX.

dalao1: segment tree &……￥#&……%……&*&%￥.

dalao2: sb block decomposition &%￥……%#￥#&……&*.

dalao3: *&……%&￥ LCT maintaining SBT easy problem &……%&……%.

edt: Not only modulo, but also multiply each number by its array index and then take modulo.

dalao: ￥%￥￥&*（#￥% gibberish gibberish.

edt: No, then throw the modulo values onto a tree and maintain the minimum range of the cactus product variance.

dalao: Use scapegoat tree with sb block linked list to maintain min-cost max-flow on Toptree and a persistent cactus, then invert in the Kirchhoff matrix and run plug DP maintained by fft. Give me three minutes, easy pass.

edt: mmp.

Problem 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