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;
using Int = long long;

template<class T, class Func = function<T(T,T)>>
struct foldMonoid{
    T e;
    const Func f;
    foldMonoid(T e_, const Func f_) : e(e_),f(f_){};
};

template<class T, class Func = function<T(T,T)>>
struct ActionMonoid{
    T e;
    const Func g,h,p;
    ActionMonoid(T e_,const Func g_, const Func h_, const Func p_) : e(e_),g(g_), h(h_), p(p_){};
};
/*
       g : T × E -> T s.t apply E to T
       h : E × E -> merge E and E
       p : E × N -> p(a,b):= g(a,a,......a ),
                               |__________|
                                    b
*/
template<class T, class Func = function<T(T,T)>>
class LazySegtree{
private:
    const size_t N;
    const ActionMonoid<T> action_monoid;
    const foldMonoid<T> fold_monoid;
    size_t offset;
    vector<T>obj, lazy;
    Func action_updater, lazy_updater;
    /* re-size vectors capacity */
    size_t bufsize(size_t num) {
        int i = 1;
        for (; (int) num + 1 > i; i <<= 1);
        offset = i - 1;
        return (i << 1) - 1;
    }
    /* update k-node*/
    void flush(int k, int l, int r){
        if(lazy[k] == action_monoid.e){
            // There is no vlaue to propagate
        } else {
            obj[k] = action_monoid.g(obj[k],action_monoid.p(lazy[k],r - l));
            // if(r - l <= 1) -> least
            if(r - l > 1) {
                lazy[2 * k + 1] = action_monoid.h( lazy[2 * k + 1],lazy[k]);
                lazy[2 * k + 2] = action_monoid.h( lazy[2 * k + 2],lazy[k]);
            }
            lazy[k] = action_monoid.e;
        }
    }
    void action(int a, int b, T val, int k, int l, int r){
        if (r < 0) r = (int)offset + 1;
        flush(k,l,r);
        if(b <= l || r <= a) return;
        if(a <= l && r <= b){
            // perfectly coverd range
            // TODO := why f???
            lazy[k] = action_monoid.h(lazy[k], val);
            flush(k, l, r);
        } else {
            action(a, b, val, 2 * k + 1, l, (l+r)/2);
            action(a, b, val, 2 * k + 2, (l+r)/2, r);
            obj[k] = fold_monoid.f(obj[2 * k + 1],obj[2 * k + 2]);
        }
    }
    T query(int a, int b, int k, int l, int r) {
        flush(k,l,r);
        if (r <= a || b <= l)return fold_monoid.e;
        if (a <= l && r <= b)return obj[k];
        else return fold_monoid.f(query(a, b, k * 2 + 1, l, (l + r) / 2), query(a, b, k * 2 + 2, (l + r) / 2, r));
    }
public:
    void action(int l,int r, T val){
        action(l,r,val,0,0,-1);
    }
    T query(int a, int b) {//[a,b)
        return query(a, b, 0, 0, (int)offset + 1);
    }
    
    LazySegtree(size_t treesize_,T init_, foldMonoid<T>foldM, ActionMonoid<T>ActionM)
    : N(treesize_),fold_monoid(foldM), action_monoid(ActionM)
    {
        obj  = vector<T>(bufsize(N), init_);
        lazy = vector<T>(bufsize(N), action_monoid.e);
        
    }
    
};
auto Add = [](Int a, Int b ) {return a + b;};
auto Mul = [](Int a, Int b ) {return a * b;};
auto g = [](int a, int b){return b;};
Int e = 0LL;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    int q; cin >> q;
    ActionMonoid<Int>act(-10000000,g,g,Mul);
    foldMonoid<Int>fm(e,Add);
    LazySegtree<Int>lsgt(n,e,fm,act);
    for(int i = 0; i < q; ++i){
        int Q; cin >> Q;
        if(Q == 1){
            int s,t; cin >> s >> t;
            ++t;
            cout << lsgt.query(s,t) << endl;
        } else {
            int s,t,x; cin >> s >> t >> x;
            ++t;
            lsgt.action(s,t,(Int)x);
        }
    }
    return 0;
}