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:
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
using ll = long long;
using P = pair<ll, ll>;
ll GCD(ll a, ll b) { return b?GCD(b, a%b):a; }
ll LCM(ll a, ll b) { return a/GCD(a, b)*b; }

template <typename T, typename E>
struct LazeSegTree {
    // 0-indexed
    typedef function<T(T, T)> F;
    typedef function<T(T, E)> G;
    typedef function<E(E, E)> H;
    int n, height;
    F f;    // クエリ処理の関数
    G g;    // 遅延伝搬を反映させる関数
    H h;    // 遅延処理の更新を行う関数
    T ti;   // クエリ処理の単位元
    E ei;   // 遅延配列の単位元
    vector<T> dat;
    vector<E> laz;
    LazeSegTree(){}
    LazeSegTree(F f, G g, H h, T ti, E ei): 
        f(f), g(g), h(h), ti(ti), ei(ei) {}
    
    // 全体を初期化
    void init(int n_) {
        n = 1, height = 0;
        while(n < n_) n <<= 1, ++height;
        dat.assign(n<<1, ti);
        laz.assign(n<<1, ei);
    }

    // 初期配列をセグ木の葉に
    void build(const vector<T> &v) {
        int n_ = v.size();
        init(n_);
        for(int i = 0; i < n_; ++i) dat[n+i] = v[i];
        for(int i = n-1; i; --i) dat[i] = f(dat[(i<<1)|0], dat[(i<<1)|1]);
    }

    // 遅延伝搬の処理を行う
    inline T reflect(int k) {
        return laz[k] == ei ? dat[k] : g(dat[k], laz[k]);
    }

    // 遅延を子ノードに伝搬
    inline void propagate(int k) {
        if(laz[k] == ei) return;
        laz[(k<<1)|0] = h(laz[(k<<1)|0], laz[k]);
        laz[(k<<1)|1] = h(laz[(k<<1)|1], laz[k]);
        dat[k] = reflect(k);
        laz[k] = ei;
    }

    inline void thrust(int k) {
        for(int i = height; i; --i) propagate(k>>i);
        dat[k] = reflect(k);
        laz[k] = ei;
    }

    // クエリ処理をマージ
    inline void recalc(int k) {
        while(k >>= 1) dat[k] = f(reflect((k<<1)|0), reflect((k<<1)|1));
    }

    void update(int a, int b, E x) {
        if(a >= b) return;
        thrust(a += n);
        thrust(b += n-1);
        for(int l = a, r = b+1; l < r; l >>= 1, r >>= 1) {
            if(l&1) laz[l] = h(laz[l], x), l++;
            if(r&1) --r, laz[r] = h(laz[r], x);
        }
        recalc(a);
        recalc(b);
    }

    // buildをバラバラに行う
    void set_val(int a, T x) {
        thrust(a += n);
        dat[a] = x; laz[a] = ei;
        recalc(a);
    }

    T query(int a, int b) {
        if(a >= b) return ti;
        thrust(a += n);
        thrust(b += n-1);
        T vl = ti, vr = ti;
        for(int l = a, r = b+1; l < r; l >>= 1, r >>= 1) {
            if(l&1) vl = f(vl, reflect(l++));
            if(r&1) vr = f(reflect(--r), vr);
        }
        return f(vl, vr);
    }

    template <typename C>
    int find(int st, C &check, T &acc, int k, int l, int r) {
        if(l+1 == r) {
            acc = f(acc, reflect(k));
            return check(acc) ? k-n : -1;
        }
        propagate(k);
        int m = (l+r)>>1;
        if(m <= st) return find(st, check, acc, (k<<1)|1, m, r);
        if(st <= 1 && !check(f(acc, dat[k]))) {
            acc = f(acc, dat[k]);
            return -1;
        }
        int vl = find(st, check, acc, (k<<1)|0, l, m);
        if(~vl) return vl;
        return find(st, check, acc, (k<<1)|1, m, r);
    }

    template <typename C>
    int find(int st, C &check) {
        T acc = ti;
        return find(st, check, acc, 1, 0, n);
    }
};

int main() {
    int n, q; cin >> n >> q;
    auto f = [](P l, P r) { return P(l.first+r.first, l.second+r.second); };
    auto g = [](P l, ll r) { return P(l.second*r, l.second); };
    auto h = [](ll l, ll r) { return r; };

    LazeSegTree<P, ll> lseg(f, g, h, P(0, 0), -1010);
    lseg.build(vector<P>(n, P(0, 1)));

    for(int i = 0; i < q; ++i) {
        int c; cin >> c;
        ll s, t, x;
        if(c) {
            cin >> s >> t;
            cout << lseg.query(s, t+1).first << endl;
        }else {
            cin >> s >> t >> x;
            lseg.update(s, t+1, x);
        }
    }
}