Dima and array 1

Mother gave Dima as a present an array of length $n$. The array is not simple, but special. Dima can choose three numbers $i,j$ and $i,j$ и $d(1\le i\le j\le n,-1000\le d\le 1000)$, and all elements with indexes from $i$ to $j$ magically become equal to $d$. Dima plays with his array, and mother gives his questions time from time — what is the sum of all the numbers in array with indexes from $f$ to $t$ inclusive? Dima easily managed this problem, but what about you?

Input

The first line contains two integers $n$ and $q(1\le n\le 5\cdot 10^5,1\le q\le 10^5)$ — the number of elements in array and the total number of operations. In the next line $n$ numbers are given: $a_1,a_2,...,a_n(-1000\le a_i\le 1000)$ — the initial state of array. The next $q$ lines contain the operations and queries. The first character in the line can be either $=$ or $?$. If the line starts with $=$, this is an assignment operation. Next values are $i,j$ and $d$, their restrictions are given earlier. If the line starts with $?$, this is a query. Then go numbers $f$ and $t(1\le f,t\le n)$.

Output

For each query print on a separate line the sum of the numbers in array with indexes from $f$ to $t$ inclusive.

Examples