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 ll = long long;
using ld = long double;
using vl = vector<ll>;
template<class T> using vc = vector<T>;
template<class T> using vvc = vector<vector<T>>;

#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define repr(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repe(i, l, r) for (ll i = (l); i < (r); i++)
#define reper(i, l, r) for (ll i = (r)-1; i >= (l); i--)
#define repa(i,n) for (auto& i: n)

template<class T> inline bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
void init() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(15);}

#ifdef DEBUG
template <class T, class N> void verr(const T& a, const N& n) { rep(i, n) cerr << a[i] << " "; cerr << "\n" << flush; }
ll dbgt = 1; void err() { cerr << "passed " << dbgt++ << "\n" << flush; }
template<class H, class... T> void err(H&& h,T&&... t){ cerr<< h << (sizeof...(t)?" ":"\n") << flush; if(sizeof...(t)>0) err(forward<T>(t)...); }
#endif

const ll INF = 4e18;
const ld EPS = 1e-11;
const ld PI = acos(-1.0L);
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
//--------------------------------------------------------------------------------//
template <class T, class U = T>
struct LazySegTree {
    int n, height;
    // 値配列, 値の単位元
    vector<T> data;
    T dataId;
    // 遅延配列, 遅延値の単位元
    vector<U> lazy;
    U lazyId;

    function<T(T, T)> fOperate;
    function<T(T, U)> fAct;
    function<U(U, U)> fMerge;

    LazySegTree(
        int _n, T _did = INF, U _lid = INF,
        function<T(T, T)> _op = [](T t1, T t2) { return min(t1, t2); },
        function<T(T, U)> _ac = [](T t1, U u1) { return u1; },
        function<U(U, U)> _me = [](U u1, U a) { return a; }
    )
        : dataId(_did), lazyId(_lid), fOperate(_op), fAct(_ac), fMerge(_me) {
        n = 1, height = 0;
        while (n < _n) n *= 2, height++;
        data = vector<T>(2 * n, dataId);
        lazy = vector<U>(2 * n, lazyId);
    }

    inline T act(int k){
        return lazy[k] == lazyId ? data[k] : fAct(data[k], lazy[k]);
    }

    inline void propagate(int k){
        if (lazy[k] == lazyId) return;
        lazy[2 * k + 0] = fMerge(lazy[2 * k + 0], lazy[k]);
        lazy[2 * k + 1] = fMerge(lazy[2 * k + 1], lazy[k]);
        data[k] = act(k), lazy[k] = lazyId;
    }


    // [a, b)を更新
    inline void update(int a, int b, U x) {
        a += n, b += n - 1;
        for (int i = height; i > 0; i--) propagate(a >> i), propagate(b >> i);
        for (int l = a, r = b + 1; l < r; l /= 2, r /= 2) {
            if (l & 1) lazy[l] = fMerge(lazy[l], x), l++;
            if (r & 1) r--, lazy[r] = fMerge(lazy[r], x);
        }
        for (int l = a / 2, r = b / 2; l > 0; l /= 2, r /= 2) {
            data[l] = fOperate(act(2 * l + 0), act(2 * l + 1));
            data[r] = fOperate(act(2 * r + 0), act(2 * r + 1));
        }
    }

    // [l, r)の区間クエリ
    inline T query(int a, int b){
        a += n, b += n - 1;
        for (int i = height; i > 0; i--) propagate(a >> i), propagate(b >> i);
        T Lret = dataId, Rret = dataId;
        for (int l = a, r = b + 1; l < r; l /= 2, r /= 2){
            if (l & 1) Lret = fOperate(Lret, act(l++));
            if (r & 1) Rret = fOperate(act(--r), Rret);
        }
        return fOperate(Lret, Rret);
    }

    inline void build(vector<T> vec){
        for (int i = 0; i < vec.size(); i++) data[i + n] = vec[i];
        for (int i = n - 1; i > 0; i--) data[i] = fOperate(data[2 * i + 0], data[2 * i + 1]);
    }

    // 添字でアクセス
    inline T& operator[](int i) {
        return data[i + n];
    }
};
// LazySegTree<T, U = T> seg(N, dataId, lazyId, fOp, fMe, fAc)
// 要素数, 要素単位元, 遅延値単位元, 要素ｘ要素, 要素ｘ作用素, 作用素ｘ作用素
// デフォルト引数　dataId = INF, lazyId = INF, fOp : min, fAct : update, fMerge : update

using P = pair<ll, ll>;
int main() {
    init();
    ll N, Q;
    cin >> N >> Q;
    auto op = [](P a, P b) { return P(a.first + b.first, a.second + b.second); };
    auto act = [](P a, ll b) { return P(a.second * b, a.second); };
    auto mer = [](ll a, ll b) { return b; };
    LazySegTree<P, ll> seg(N, P(0, 1), INF, op, act, mer);
    seg.build(vc<P>(N, P(0, 1)));

    ll ans = 0;
    rep(_, Q){
        ll q, a, b;
        cin >> q >> a >> b;
        if(q==0){
            ll x;
            cin >> x;
            seg.update(a, b + 1, x);
        }else{
            cout << seg.query(a, b + 1).first << '\n';
        }
    }
}