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(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(ll i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD 1000000007
#define P pair<ll, ll>

//つよいせぐつりー！(RUQ+RAQ) ばぐってるかも
struct LazySegTree { //参照は + sz - 1;
	ll sz;
	vector<ll> node, lazy;
	vector<bool> lazyFlag;
	LazySegTree(ll n) {
		sz = 1;
		while (sz < n) sz *= 2;
		node.resize(2 * sz - 1);//
		lazy.resize(2 * sz - 1);//
		lazyFlag.resize(2 * sz - 1);
	}
	void eval(ll k, ll l, ll r) {
		if (lazyFlag[k]) {
			node[k] = lazy[k];//
			if (r - l > 1) {
				lazy[2 * k + 1] = lazy[k] / 2;//
				lazy[2 * k + 2] = lazy[k] / 2;//
				lazyFlag[2 * k + 1] = lazyFlag[2 * k + 2] = true;
			}
			lazyFlag[k] = false;
			lazy[k] = 0;//
		}
		else {
			if (lazy[k] == 0)return;
			node[k] += lazy[k];//
			if (r - l > 1) {
				lazy[2 * k + 1] += lazy[k] / 2;//
				lazy[2 * k + 2] += lazy[k] / 2;//
			}
			lazy[k] = 0;//
		}
	}
	void add(ll a, ll b, ll x, ll k = 0, ll l = 0, ll r = -1) {
		if (r < 0) r = sz;
		eval(k, l, r);
		if (b <= l || r <= a) return;
		if (a <= l && r <= b) {
			lazy[k] += (r - l) * x;//
			eval(k, l, r);

		}
		else {
			add(a, b, x, 2 * k + 1, l, (l + r) / 2);
			add(a, b, x, 2 * k + 2, (l + r) / 2, r);
			node[k] = node[2 * k + 1] + node[2 * k + 2];//
		}
	}
	void update(ll a, ll b, ll x, ll k = 0, ll l = 0, ll r = -1) {
		if (r < 0) r = sz;
		eval(k, l, r);
		if (b <= l || r <= a) return;
		if (a <= l && r <= b) {
			lazy[k] = (r - l) * x;//	
			lazyFlag[k] = true;
			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] = node[2 * k + 1] + node[2 * k + 2];//
		}
	}
    void add(ll a, ll x) {
		add(a, a + 1, x);
	}
	void update(ll a, ll x) {
		update(a, a + 1, x);
	}
	ll query(ll a, ll b, ll k = 0, ll l = 0, ll r = -1) {
		if (r < 0) r = sz;
		eval(k, l, r);
		if (b <= l || r <= a) return 0;//
		if (a <= l && r <= b) return node[k];
		ll vl = query(a, b, 2 * k + 1, l, (l + r) / 2);
		ll vr = query(a, b, 2 * k + 2, (l + r) / 2, r);
		return vl + vr;//
	}
	void init() {
		REPR(i, sz - 2) node[i] = node[2 * i + 1] + node[2 * i + 2];//
	}
};

int main() {
    ll n, q;
    cin >> n >> q;
    LazySegTree seg(n);
    REP(i, q){
        ll t;
        cin >> t;
        if(t == 0){
            ll a, b, c;
            cin >> a >> b >> c;
            seg.update(a, b + 1, c);
            seg.add(a, b + 1, c);
            seg.add(a, b + 1, -c);
        }
        else{
            ll a, b;
            cin >> a >> b;
            cout << seg.query(a, b + 1) << endl;
        }
    }
}