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(1\le n\le 10^5,0\le k\le 10^5)$ — the number of elements in array and the number of queries. The next $k$ lines contain the queries of two forms:

• $Alrx$ — 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)$

• $Qlr$ — 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

For each query of the form "$Qlr$" print the sum of numbers on a segment.

Examples