Problem: Write a program which manipulates a sequence $A$ = {$a_0, a_1, ..., a_{n-1}$} with the following operations:

* $update(s, t, x)$: change $a_s, a_{s+1}, ..., a_t$ to $x$.
* $getSum(s, t)$: print the sum of $a_s, a_{s+1}, ..., a_t$.



Note that the initial values of $a_i ( i = 0, 1, ..., n-1 )$ are 0.

Constraints

* $1 ≤ n ≤ 100000$
* $1 ≤ q ≤ 100000$
* $0 ≤ s ≤ t < n$
* $-1000 ≤ x ≤ 1000$

Input


$n$ $q$
$query_1$
$query_2$
:
$query_q$


In the first line, $n$ (the number of elements in $A$) and $q$ (the number of queries) are given. Then, $i$-th query $query_i$ is given in the following format:


0 $s$ $t$ $x$


or


1 $s$ $t$


The first digit represents the type of the query. '0' denotes $update(s, t, x)$ and '1' denotes $find(s, t)$.

Output

For each $getSum$ query, print the sum in a line.

Example

Input

6 7
0 1 3 1
0 2 4 -2
1 0 5
1 0 1
0 3 5 3
1 3 4
1 0 5


Output

-5
1
6
8

Solution (in PYTHON3):

Solution:
import sys
input = sys.stdin.readline

n, q = map(int, input().split())

Len = (n-1).bit_length()
size = 2**Len
tree = [0]*(2*size)
lazy = [None]*(2*size)
h = [None]
for i in range(Len+1):
    v = 2**(Len-i)
    h += [v]*(2**i)

def gindex(l,r):
    L = (l+size)>>1;R=(r+size)>>1
    lc = 0 if l & 1 else (L&-L).bit_length()
    rc = 0 if r & 1 else (R&-R).bit_length()
    for i in range(Len):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1
        
def propagates(ids):
    for i in reversed(ids):
        v = lazy[i]
        if v is None:
            continue
        lazy[2*i] = tree[2*i] = lazy[2*i+1] = tree[2*i+1] = v//2
        lazy[i]=None

def update(l,r,x):
    *ids, = gindex(l, r)
    propagates(ids)
    L = size+l
    R = size+r
    while L<R:
        if R&1:
            R -= 1
            lazy[R] = tree[R] = x*h[R]
        if L&1:
            lazy[L] = tree[L] = x*h[L]
            L+=1
        L>>=1;R>>=1
    for i in ids:
        if 2*i+1<size*2:
            tree[i]= tree[i*2]+tree[i*2+1]
        
def query(l, r):
    *ids, = gindex(l, r)
    propagates(ids)
    L = size + l
    R = size + r
    s = 0
    while L<R:
        if R&1:
            R-=1
            s +=tree[R]
        if L&1:
            s +=tree[L]
            L+=1
        L>>=1;R>>=1
    return s

ans = []
for i in range(q):
    a, *b = map(int, input().split())
    if a:
        ans.append(query(b[0],b[1]+1))
    else:
        update(b[0],b[1]+1,b[2])
print('\n'.join(map(str,ans)))