You are given a sequence A[1], A[2],..., A[N]. On this sequence you have to apply M operations: Add all the elements whose value are in range [l, r] by d or, ask for a query how many element are in range [l, r].

Input

There are only one case in each input file, process until the end of the file. The first line of each case contains two numbers, N, M, described as above. And then start from the second line, have N numbers described the sequence's initial value.

( 1≤ N ≤ 250,000, M ≤ 50,000), |A[i]| ≤ 1,000,000,000 .)

The following M lines described the operation:

• C l r d: Add all the element whose value are in range [l, r] by d. (Redeclare: Not its Position! .. )
• Q l r: ask for a query how many elements, whose value are in range [l, r].

(l ≤ r, |l|、|r|、|d|≤ 1,000,000,000. notes [l, r] are closed interval, i.e not less than l and not greater than r. )

We guarantee every elements are suits 32-integer, and will not cause overflow, even during the running-time. (.. but still be careful ;) Besides, all the test-data are generated randomly.

Output

For each query, print the result.

Example

Input 1:
10 3
1 2 3 4 5 6 7 8 9 10
C 6 10 5
C 1 5 -5
Q 1 10

Output 1:
0

Input 2:
10 10
10 4 -5 8 8 3 0 -2 4 7
C -9 8 2
C -4 10 -3
C -10 0 5
Q -9 -1
C -9 -5 8
C -7 4 3
Q -2 7
C -10 -3 2
C -4 -1 -6
Q 7 10

Output 2:
1
10
4

(In the first example, after the two operations, the sequences are become to, 
{-4, -3, -2, -1, 0, 11, 12, 13, 14, 15}, so there are no elements whose value are in range [1, 10]. )

Warning: large input/output data,be careful with certain languages