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:
/*
参考
https://ei1333.github.io/luzhiled/snippets/structure/segment-tree.html

https://firiexp.github.io/library/library/lazysegtree.html

https://smijake3.hatenablog.com/entry/2018/11/03/100133#%E9%81%85%E5%BB%B6%E8%A9%95%E4%BE%A1%E3%82%BB%E3%82%B0%E3%83%A1%E3%83%B3%E3%83%88%E6%9C%A8%E3%81%AE%E6%A6%82%E8%A6%81
verify:
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_F
*/

#pragma GCC optimize("Ofast")
#include <cstdio>
#include <cstdlib>
#include <string>
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
#include <bitset>
#include <cmath>
#include <limits>
#include <iostream>
#include <map>
#include <set>
#include <tuple>
#include <iomanip>
#include <functional>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
typedef pair<ll,ll> pll;

template<class T,class U>constexpr bool chmin(T&a,const U b){if(a<=b)return false;a=b;return true;}
template<class T,class U>constexpr bool chmax(T&a,const U b){if(a>=b)return false;a=b;return true;}
#define bit(n,k) ( (n>>k)&1 )

//デバッグ
template<class T>
void Vout(vector<T> &V){
    cout<<"\nstart\n";
    const int sz=V.size();
    for(int i=0;i<sz;i++){
        cout<<i<<" "<<V[i]<<'\n';
    }
    cout<<"end\n"<<endl;
}

template<class T>
void VPout(vector<T> &V){
    cout<<"\nstart\n";
    const int sz=V.size();
    for(int i=0;i<sz;i++){
        cout<<i<<" "<<V[i].first<<" "<<V[i].second<<'\n';
    }
    cout<<"end\n"<<endl;
}


//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++


constexpr int MAX=1<<30;
constexpr ll INF=1LL<<62;
constexpr int MOD=1e9+7;
int dx[]={1,-1,0,0},dy[]={0,0,-1,1};

//__builtin_popcount(S);
//#define int ll
//vector<vector<int>> data(3, vector<int>(4));
//vector.resize(a,vector<int>(b,-1));
//vector<vector<vector<要素の型>>> 変数名(要素数1, vector<vector<要素の型>>(要素数2, vector<要素の型>(要素数3, 初期値)));


template<typename T,typename L>
struct LazySegmentTree{
    //using
    using F=function<T(T,T)>;
    using G=function<T(T,L)>;
    using H=function<L(L,L)>; //二番目が後に追加されたもの

    //データ
    int sz;
    int height;
    vector<T> seg;
    vector<L> lazy;
    const T sut;
    const L lut;
    const F f;
    const G g;
    const H h;

    LazySegmentTree(int n,const T sut,const L lut,const F &f,const G &g,const H &h):sut(sut),lut(lut),f(f),g(g),h(h){
        sz=1;
        height=0;
        while(sz<n) sz<<=1,height++;
        seg.assign((sz<<1),sut);
        lazy.assign((sz<<1),lut);        
    }

    inline void set(int k,const T &x){
        seg[k+sz]=x;
    }
    inline void build(){
        for(int k=sz-1;k>0;k--){
            seg[k]=f(seg[(k<<1)],seg[(k<<1)+1]);
        }
    }
    inline T reflect(int k){
        return (lazy[k]==lut) ? seg[k]:g(seg[k],lazy[k]);
    }
    //子にlazyを伝える(updateで丸々収まる所を更新した尻ぬぐい)
    //lazy[k]とlazy[2*k]が違った場合,lazy[k]の方が後に更新されたもの
    inline void propagate(int k){
        if(lazy[k]!=lut){
            lazy[(k<<1)]=h(lazy[(k<<1)],lazy[k]);
            lazy[(k<<1)+1]=h(lazy[(k<<1)+1],lazy[k]);
            seg[k]=reflect(k);
            lazy[k]=lut;
        }
    }
    //ボトムアップで更新していく
    inline void recalc(int k){
        while(k>>=1) seg[k]=f(reflect((k<<1)),reflect((k<<1)+1));
    }
    //トップダウンで更新していく(これでseg[k]が正しい値になる)
    inline void thrust(int k){
        for(int i=height;i>0;i--) propagate(k>>i);
    }
    void update(int a,int b,const L &x){
        //トップダウンでlazy[i]!=lutのものを更新
        thrust(a+=sz);
        thrust(b+=sz-1);
        //丸々収まるところを更新
        for(int l=a,r=b+1;l<r;l>>=1,r>>=1){
            if(l&1) lazy[l]=h(lazy[l],x),l++;
            if(r&1) --r,lazy[r]=h(lazy[r],x);
        }
        //ボトムアップで新しく更新
        recalc(a);
        recalc(b);
    }

    //[a:b)
    T query(int a,int b){
        //トップダウンで関係あってlazy[i]!=lutのものを更新
        thrust(a+=sz);
        thrust(b+=sz-1);
        //更新した後は普通のセグ木と同じ
        T l=sut,r=sut;
        for(a,b+=1;a<b;a>>=1,b>>=1){

            if(a&1) l=f(l,reflect(a++));
            if(b&1) r=f(reflect(--b),r);
        }
        return f(l,r);
    }
    //セグ木と違い、log(n)かかる
    T operator[](const int k){
        return query(k,k+1);
    }

};

//[](int a,int b){return min(a,b);}

signed main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
    int n,q;
    cin>>n>>q;
    auto f=[](pii a,pii b){return pii(a.first+b.first,a.second+b.second);};
    auto g=[](pii a,int b){return pii(a.first,a.first*b);};
    auto h=[](int a,int b){return b;};
    LazySegmentTree<pii,int> l(n,pii(0,0),-1100,f,g,h);
    for(int i=0;i<n;i++){
        l.set(i,pii(1,0));
    }
    l.build();
    while(q--){
        int a;
        cin>>a;
        if(a==0){
            int s,t,x;
            cin>>s>>t>>x;
            l.update(s,t+1,x);
        }else{
            int s,t;
            cin>>s>>t;
            cout<<l.query(s,t+1).second<<endl;
        }
    }

}