eolymp
bolt
Try our new interface for solving problems
Problems

The sum

The sum

Time limit 1 second
Memory limit 128 MiB

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

Input data

The first line contains two integers n and k~(1 \le n ≤ 10^5, 0 ≤ k ≤ 10^5) — 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~(1 \le l \le r \le n, 0 \le x \le 10^9)

  • Q~l~r — find the sum of array elements on positions from l to r~(1 \le l \le r \le n)

Initially the array is filled with zeroes.

Output data

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

Examples

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