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<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define LINF (ll)INF*INF
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(int i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

#define int ll //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef vector<pii> vp;
typedef pair<pii,int> ppi;

int gcd(int a, int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int lcm(int a, int b){
    return a/gcd(a,b)*b;
}

class LazySegmentTree{
private:
    int n;
    vector<long long> node, lazy;
    long long node_init = 0; // sum, max, update
    //long long node_init = LINF; // min
    //long long lazy_init = 0; // default
    long long lazy_init = LINF; // min, update (存在しない値)

    long long lazy_update(long long a,long long b){
        //return a+b; // sum query
        //return max(a,b); // max query
        //return min(a,b); // min query
        return b; // update query
    }

    long long node_update(long long a, long long b, int l, int r){ // lazy を node に反映
        //return a + b; // min query
        //return b; // update query
        return b * (r-l); // sum query
    }

    long long combine(long long a,long long b){
        return a+b; // sum query
        //return max(a,b); // max query
        //return min(a,b); // min query
    }

public:
    LazySegmentTree(){}
    LazySegmentTree(vector<long long> in){
        n = 1;
        while(n < in.size())n <<= 1;
        node = vector<long long>(2*n, node_init);
        lazy = vector<long long>(2*n, lazy_init);
        for(int i = n-1+in.size()-1; i >= 0; i--){
            if(n-1 <= i)node[i] = in[i-(n-1)];
            else node[i] = combine(node[i*2+1], node[i*2+2]);
        }
    }
    void eval(int k, int l, int r){
        if(lazy[k] != lazy_init){
            node[k] = node_update(node[k], lazy[k], l, r);
            if(r - l > 1){
                lazy[2*k+1] = lazy_update(lazy[2*k+1], lazy[k]);
                lazy[2*k+2] = lazy_update(lazy[2*k+2], lazy[k]);
            }
            lazy[k] = lazy_init;
        }
    }
    void update(int a, int b, long long x, int k = 0, int l = 0, int r = -1){
        if(r < 0)r = n;
        eval(k,l,r);
        if(b <= l || r <= a)return;
        if(a <= l && r <= b){
            lazy[k] = x;
            eval(k,l,r);
        }else{
            update(a,b,x,2*k+1,l,(l+r)/2);
            update(a,b,x,2*k+2,(l+r)/2,r);
            node[k] = combine(node[2*k+1], node[2*k+2]);
        }
    }
    long long query(int a, int b, int k = 0, int l = 0, int r = -1){
        if(r < 0)r = n;
        if(b <= l || r <= a)return node_init;
        eval(k,l,r);
        if(a <= l && r <= b)return node[k];
        return combine(query(a,b,2*k+1,l,(l+r)/2), query(a,b,2*k+2,(l+r)/2,r));
    }
    void show(){
        cout << "node :";
        for(int i = 0; i < 2*n-1; i++){
            if(i == n-1)cout << "     ";
            cout << " " << node[i];
        }
        cout << endl;
        cout << "lazy :";
        for(int i = 0; i < 2*n-1; i++){
            if(i == n-1)cout << "     ";
            cout << " " << lazy[i];
        }
        cout << endl;
    }
};

signed main(void) {
    int n,q;
    cin >> n >> q;
    LazySegmentTree lazy = LazySegmentTree(vi(n));

    rep(i,q){
        int a;
        cin >> a;
        if(a == 0){//update
            int s,t,x;
            cin >> s >> t >> x;
            lazy.update(s,t+1,x);
        }else{//query
            int s,t;
            cin >> s >> t;
            cout << lazy.query(s,t+1) << endl;
        }
        //lazy.show();
    }

}