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 CPP):

Solution:
/*
 * Lazy Segment Tree
 * Construction: O(n)
 * Update:       O(log n)
 * Query:        O(log n)
 *
 * Memory Usage: 3n
 */

#include <vector>
#include <cstdio>
using namespace std;

class SegmentTree {
    const int N; // array size
    const int M; // initial value
    const int O; // initial value of the query
    const int H; // height of the tree, the highest significant bit in N

    int (*f)(int, int); // query operation
    int (*g)(int, int); // update operation
    int (*h)(int, int); // delayed operation

public:
    vector<int> t; // tree
    vector<int> d; // delayed tree
    vector<bool> u; // is delayed

    SegmentTree(int N, int M, int O, int (*f)(int, int), int (*g)(int, int), int (*h)(int, int)) :
            N(N), M(M), O(O), H(sizeof(int) * 8 - __builtin_clz(N)),
            f(f), g(g), h(h), t(2 * N, M), d(N), u(N) {}

    void init() { // init tree from leaves
        for (int i = N - 1; i > 0; --i)
            t[i] = f(t[i << 1], t[i << 1 | 1]);
    }

    void set(int k, int val) { // direct edit
        t[k + N] = val;
    }

    void apply(int p, int val, int k) { // propagate helper
        t[p] = g(h(val, k), t[p]);
        if (p < N) {
            d[p] = g(val, d[p]);
            u[p] = true;
        }
    }

    void calc(int p, int k) { // build helper
        if (u[p]) t[p] = h(d[p], k);
        else t[p] = f(t[p << 1], t[p << 1 | 1]);
    }

    void build(int p) { // build from p th node to root
        int k = 2;
        for (p += N; p > 1; k <<= 1) {
            p >>= 1;
            calc(p, k);
        }
    }

    void propagate(int p) { // propagate to p th node from root
        p += N;
        for (int s = H, k = 1 << (H - 1); s > 0; --s, k >>= 1) {
            int i = p >> s;
            if (u[i]) {
                apply(i << 1, d[i], k);
                apply(i << 1 | 1, d[i], k);
                d[i] = 0;
                u[i] = false;
            }
        }
    }

    void update(int l, int r, int val) { // set val at interval [l, r)
        propagate(l);
        propagate(r - 1); // make sure old propagation is completed

        int k = 1; // interval level
        int l0 = l, r0 = r;
        l += N, r += N;

        for (; l < r; l >>= 1, r >>= 1, k <<= 1) {
            if (l & 1) apply(l++, val, k);
            if (r & 1) apply(--r, val, k);
        }

        build(l0);
        build(r0 - 1);
    }

    int query(int l, int r) { // query on interval [l, r)
        propagate(l);
        propagate(r - 1);
        int res = O;
        for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res = f(t[l++], res);
            if (r & 1) res = f(t[--r], res);
        }
        return res;
    }
};

void put_int(int n) {
    if (!n) {
        putchar_unlocked('0');
        return;
    }
    if (n < 0) n = -n, putchar_unlocked('-');
    char buf[11];
    int i = 0;
    while (n) buf[i++] = (char) (n % 10 + '0'), n /= 10;
    while (i--)putchar_unlocked(buf[i]);
}

int get_int() {
    int n = 0;
    int c = getchar_unlocked();
    if (c == 45) {
        c = getchar_unlocked();
        while (47 < c && c < 58) n = 10 * n + (c & 0xf), c = getchar_unlocked();
        return -n;
    } else if (c < 48 || 57 < c) return c;
    while (47 < c && c < 58) n = 10 * n + (c & 0xf), c = getchar_unlocked();
    return n;
}

void test() {
    int n = get_int();
    int q = get_int();
    SegmentTree T(n, 0, 0,
                  [](int a, int b) { return a + b; },
                  [](int a, int b) { return a; },
                  [](int a, int b) { return a * b; }
    );

    while (q--) {
        int type = get_int();
        if (type) {
            int s = get_int();
            int t = get_int();
            put_int(T.query(s, t + 1));
            putchar_unlocked('\n');
        } else {
            int s = get_int();
            int t = get_int();
            int x = get_int();
            T.update(s, t + 1, x);
        }
    }
}

int main() {
    test();
}