# The sum

Easy

Execution time limit is 1 second

Runtime memory usage limit is 128 megabytes

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≤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:

$Alrx$ — assign the value of $x$ to each element form position $l$ to $r(1≤l≤r≤n,0≤x≤10_{9})$

$Qlr$ — find the sum of array elements on positions from $l$ to $r(1≤l≤r≤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

Input #1

Answer #1

Submissions 4K

Acceptance rate 26%