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? \InputFile 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)$. \OutputFile For each query print on a separate line the sum of the numbers in array with indexes from $f$ to $t$ inclusive.