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:
#!/usr/bin/env python3
# DSL_2_I: RSQ and RUQ
# Range Sum Query and Range Update Query

import sys


class SegmentTree:

    def __init__(self, n):
        size = 2 ** (n.bit_length())
        self.size = 2*size - 1
        self.data = [0] * self.size
        self.lazy = [None] * self.size

    def update(self, lo, hi, v):
        def _update(r, i, j, lz):
            left, right = r*2 + 1, r*2 + 2
            if lz is None:
                lz = lazy[r]
            lazy[r] = None

            if lo <= i and j <= hi:
                data[r] = v * (j - i + 1)
                if i < j:
                    lazy[left] = v
                    lazy[right] = v
            else:
                mid = (i + j) // 2
                if mid >= lo:
                    lv = _update(left, i, mid, lz)
                else:
                    if lz is not None:
                        lazy[left] = lz
                        lv = lz * (mid - i + 1)
                    elif lazy[left] is not None:
                        lv = lazy[left] * (mid - i + 1)
                    else:
                        lv = data[left]

                if mid < hi:
                    rv = _update(right, mid+1, j, lz)
                else:
                    if lz is not None:
                        lazy[right] = lz
                        rv = lz * (j - mid)
                    elif lazy[right] is not None:
                        rv = lazy[right] * (j - mid)
                    else:
                        rv = data[right]

                data[r] = lv + rv

            return data[r]

        data = self.data
        lazy = self.lazy
        _update(0, 0, self.size//2, None)

    def sum(self, lo, hi):
        def _sum(r, i, j, lz):
            if lz is None:
                lz = lazy[r]
            lazy[r] = None
            if lz is not None:
                data[r] = lz * (j - i + 1)

            left, right = r*2 + 1, r*2 + 2
            if lo <= i and j <= hi:
                if lz is not None and i < j:
                    lazy[left] = lz
                    lazy[right] = lz
                return data[r]
            else:
                mid = (i + j) // 2
                lv, rv = 0, 0

                if mid >= lo:
                    lv = _sum(left, i, mid, lz)
                else:
                    if lz is not None:
                        lazy[left] = lz
                if mid < hi:
                    rv = _sum(right, mid+1, j, lz)
                else:
                    if lz is not None:
                        lazy[right] = lz
                return lv + rv

        data = self.data
        lazy = self.lazy
        return _sum(0, 0, self.size//2, None)


def run():
    n, q = [int(i) for i in input().split()]
    tree = SegmentTree(n)

    for line in sys.stdin:
        com, *args = line.split()
        if com == '0':
            s, t, x = [int(i) for i in args]
            tree.update(s, t, x)
        elif com == '1':
            s, t = [int(i) for i in args]
            print(tree.sum(s, t))


if __name__ == '__main__':
    run()