Array Range Update and Modular Query

We are given an array of length ( n ) (indexed from 1) initially filled with zeros. You need to process two types of operations:

1. ( A\ L\ R\ X ): For every index ( i ) in the interval ( [L, R] ), add ( X ) to the element at index ( i ).

2. ( Q\ L\ R ): For each index ( i ) in ( [L, R] ), check whether ( ((a[i])\times i \mod mod) ) is within the range ( [min, max] ) (inclusive). Output the count of such indices.

It is guaranteed that the number of non-delayed query operations does not exceed ( 1000 ). After all modification operations, there may be a large number of delayed query operations (up to ( 10^7 ) queries), but no further modifications will appear afterwards.

Note: All arithmetic is performed in the standard integer range and the modulo operation uses the given ( mod ).

inputFormat

The first line contains five integers separated by spaces: ( n ), ( opt ), ( mod ), ( min ), and ( max ), where:

• ( n ) is the number of elements in the array.
• ( opt ) is the total number of operations.
• ( mod ) is the modulus used in the query calculations.
• ( min ) and ( max ) define the inclusive range in which ( (a[i] \times i \mod mod) ) must lie.

Each of the following ( opt ) lines represents an operation in one of the following formats:

• For an update operation: ( A\ L\ R\ X ) which means for each index ( i ) in ( [L, R] ), add ( X ) to ( a[i] ).

• For a query operation: ( Q\ L\ R ) which means count the number of indices ( i ) in ( [L, R] ) where ( min \leq ((a[i])\times i \mod mod) \leq max ).

The array is 1-indexed.

outputFormat

For each query operation ( Q ), output a single integer — the count of indices satisfying the condition ( min \leq ((a[i])\times i \mod mod) \leq max ) — on a new line.

sample

5 5 100 10 50
A 1 3 10
Q 1 5
A 2 5 5
Q 2 4
Q 1 1

3
3
1