e-olymp
Problems

The sum

The sum

The array of n elements is given. Find the sum of numbers on a segment.

Input

The first line contains two integers n and k (1n105, 0k105) - the number of elements in array and the number of queries. The next k lines contain the queries of two forms:

  • A l r x - assign the value of x to each element form position l to r (1lrn, 0x109)
  • Q l r - find the sum of array elements on positions from l to r (1lrn)

Initially the array is filled with zeroes.

Output

For each query of the form "Q l r" print the sum of numbers on a segment.

Time limit 1 second
Memory limit 128 MiB
Input example #1
5 9
A 2 3 2
A 3 5 1
A 4 5 2
Q 1 3
Q 2 2
Q 3 4
Q 4 5
Q 5 5
Q 1 5
Output example #1
3
2
3
4
2
7