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;

#define rep(i,n) for(i = 0;i < n;++i)
#define all(v) v.begin(), v.end()
using ll = long long;

template <typename T>
struct SegmentTreeLazy //デフォルトは区間変更区間合計
{
    int n;
    const T ex = 0; //dat 初期値(合計なので)
    const T em = 1ll << 60; //lazy 初期値(updateするので)
    //lazyで一括更新をもって、datでqueryに対応する。
    vector<T> dat, lazy, weight; //tree本体
    SegmentTreeLazy(vector<T> v){
        int x = 1;
        int i;
        n = v.size();
        while(x < n) x <<= 1;
        n = x; 
        dat.resize(2*n-1, ex); //tree本体
        lazy.resize(2*n-1, em); //遅延評価
        weight.resize(2*n-1, 0); //何node持ってるか
        for(i = 0;i < v.size();++i){
            dat.at(i + n - 1) = v.at(i);
            weight.at(i + n - 1) = 1;
        }
        for(i = n-2;i >= 0;--i){
            dat.at(i) = fx(dat.at(2*i+1), dat.at(2*i+2));
            weight.at(i) = weight.at(2*i + 1) + weight.at(2*i + 2);
        }
    }
    
    T fx(T a, T b){ //dat上での計算
        return a + b; //区間加算なので加算
    }

    T fm(T a){ //lazy上での計算
        return min(a, em);
    }
    
    void eval(int now){ //区間下は全て影響を受ける。(受ける時しか呼ばれない)
        if(lazy.at(now) == em) return;
        if(now < n - 1){ //区間加算なので値を代入する。
            lazy.at(2*now + 1) = fm(lazy.at(now));
            lazy.at(2*now + 2) = fm(lazy.at(now));
        }
        //**********************ここが大事
        dat.at(now) = lazy.at(now)*weight.at(now); //区間加算する。
        //**********************
        lazy.at(now) = em;
    }
    
    void update(int a, int b, T x, int now, int l, int r){
        eval(now);
        if(a <= l && r<= b){ //区間内に全部いる。
            lazy.at(now) = x; //上から書き換える。区間最小なので同じ値を足す。
            eval(now);
        }else if(a < r && l < b){
            update(a, b, x, 2*now + 1, l, (l + r)/2);
            update(a, b, x, 2*now + 2, (l + r)/2, r);
            dat.at(now) = fx(dat.at(2*now + 1), dat.at(2*now + 2));
        }
    }
    void update(int a, int b, T x){update(a, b, x, 0, 0, n);}
    
    T query(int a, int b){return query_sub(a, b, 0, 0, n);}
    T query_sub(int a, int b, int now, int l, int r){
        eval(now);
        if(r <= a || b <= l) return ex;
        else if(a <= l && r <= b) return dat.at(now);
        else{
            T vl = query_sub(a, b, 2*now + 1, l, (l + r)/2);
            T vr = query_sub(a, b, 2*now + 2, (l + r)/2, r);
            return fx(vl, vr);
        }
    }

    inline T operator[](int a) { return query(a, a + 1); }
    void print() {
        for (int i = 0; i < 2 * n - 1; ++i) {
            cout << (*this)[i];
            if (i != n) cout << ",";
        }
        cout << endl;
    }
};

int main()
{
    ll i,j;
    ll n,q;
    cin >> n >> q;
    vector<ll> a(n, 0);
    SegmentTreeLazy<ll> seg(a);
    for(i = 0;i < q;++i){
        ll com;
        cin >> com;
        if(com == 0){
            ll s,t,x;
            cin >> s >> t >> x;
            seg.update(s, t+1, x);
        }else{
            ll s,t;
            cin >> s >> t;
            cout << seg.query(s, t+1) << endl;
        }
    }

    return 0;
}