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≤i≤j≤n,−1000≤d≤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?
The first line contains two integers n and q(1≤n≤5⋅105,1≤q≤105) — the number of elements in array and the total number of operations. In the next line n numbers are given: a1,a2,...,an(−1000≤ai≤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≤f,t≤n).
For each query print on a separate line the sum of the numbers in array with indexes from f to t inclusive.