Problem Background

Introduction

Mastering data structures ensures a stress-free future.

Edgration, a novice in data structures (referred to as edt), once challenged a group of experts:

edt wanted a data structure that could perform range addition and count elements greater than k in a given range.

Expert 1: Simple segment tree.

Expert 2: Simple block partitioning.

Expert 3: Simple balanced tree.

edt: No, let's add modulo operation and count elements within a range after modulo.

Expert 1: Segment tree...

Expert 2: Simple block partitioning...

Expert 3: LCT maintaining SBT, a piece of cake...

edt: Not enough, multiply each number by its index and then modulo.

Experts: ...

edt: Still not enough, put the modulo results on a tree and maintain the minimum variance of the cactus product.

Experts: Using a scapegoat tree with a block list to maintain the minimum cost maximum flow on a Top tree, calculate it in the Kirchhoff matrix, and then run FFT for plug-in DP. Give me three minutes to easily solve it...

edt: ...

Problem Description

Novice Edt has handed this problem over to you—a master in data structures. As it's the first question, it's not that hard.

Edt has simplified the problem as follows:

• The initial array elements are all zeros.
• Given \( n \), \( opt \), \( mod \), \( min \), \( max \), where \( mod \) is within the int range.
• Operations \( A \) and \( Q \).

\( A \): \( L \), \( R \), \( X \) means adding \( X \) to the interval \([L, R]\) (each element in the array from \( L \) to \( R \) is increased by \( X \)).

\( Q \): \( L \), \( R \) means querying the count of elements \( T \) in the interval \([L, R]\) such that \( min \leq (T \times i \mod mod) \leq max \) (the value of the element multiplied by its index modulo \( mod \) is within the range \([min, max]\)).

Due to the intervention of a non-dimensional hamster, some queries are delayed into chaotic time. Your query operations will not exceed 1000 times. Unfortunately, there may be many delayed query operations (less than 1e7 times), but there will be no further modification operations after these delayed queries.

Input Format

Given \( n \), \( opt \), \( mod \), \( min \), \( max \) representing the sequence size, number of operations, modulo, minimum value, and maximum value.

Next, \( opt \) lines:

\( A \): \( L \), \( R \), \( X \) indicates range addition, ensuring \( X \) is within the int range (< 2147483647).

\( Q \): \( L \), \( R \) indicates range query for the count of elements meeting the condition.

Then, a \( Final \) value indicates there are \( Final \) queries.

Next, \( Final \) lines:

\( L \), \( R \) indicates querying the interval \([L, R]\) for the count of elements meeting the condition.

Output Format

For each \( Q \) operation, output the count of elements meeting the condition.

Next, \( Final \) lines for the \( Final \) queries.

Sample Input and Output

Input Sample #1

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

Output Sample #1

1
2
1
1
1
0

Input Sample #2

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

Output Sample #2

3
6
7
8
2

Input Sample #3

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

Output Sample #3

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

Notes

Sample Explanation

For Sample 1:

The array \( a \) is modified to \([5, 5, 5]\).

Each \( a[i] \times i \mod 4 \) value is \([1, 2, 3]\).

For the final queries:

The count of elements greater than or equal to 0 and less than or equal to 2 in the interval \([1, 3]\) is 2.

The remaining queries follow similarly.

Problem Notes

Note:

1. Regarding modulo of negative numbers, follow the C++ standard of rounding towards zero, e.g., \([-7 \mod 3 = -1]\), \([7 \mod 3 = 1]\).

2. There will be 50 test cases, each worth 2 points.

Due to the large number of test cases, please refrain from submitting multiple times intentionally to overload the judge. The problem setter, edt, expresses sincere gratitude.

Data Range

If you cannot solve all points, try to get partial scores. All data is randomly generated.

见题面 Input 部分

见题面 Output 部分