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;

/*
	UNITY_NODE sumの単位元
	UNITY_LAZY updateの単位元
	nodeの初期値に注意(init)
	addの呼び出し元に注意(区間の長さに比例する)
	上の関係でUNITY_LAZY / 2も単位元とみなしている
*/
template <class NODE, class LAZY, NODE UNITY_NODE, LAZY UNITY_LAZY>
struct LazySegTree {
// edit start
	void add(LAZY &a, LAZY b) {
		if (b == UNITY_LAZY || b == UNITY_LAZY / 2) return;
		a = b;
	}
	void reflect(NODE& a, LAZY b, int l, int r) {
		if (b == UNITY_LAZY || b == UNITY_LAZY / 2) return;
		a = b;
	}
	NODE merge(NODE a, NODE b) {
		return a + b;
	}
// end
	int n;
	vector<NODE> node;
	vector<LAZY> lazy;
	LazySegTree(int sz) {
		init(sz);
	}
	void init(int sz) {
		n = 1;
		while (n < sz) n *= 2;
		node.assign(2*n-1, 0);
		lazy.assign(2*n-1, UNITY_LAZY);
	}
	void eval(int l, int r, int k) {
		reflect(node[k], lazy[k], l, r);
		if (r - l > 1) {
			add(lazy[k*2+1], lazy[k] / 2);
			add(lazy[k*2+2], lazy[k] / 2);
		}
		lazy[k] = UNITY_LAZY;
	}
	void renode(int k) {
		node[k] = merge(node[k*2+1], node[k*2+2]);
	}
	void set(int a, int b, LAZY x, int k=0, int l=0, int r=-1) {
		if (r < 0) r = n;
		if (b <= l || r <= a) {
			eval(l, r, k);
		} else if (a <= l && r <= b) {
			add(lazy[k], x * (r - l));
			eval(l, r, k);
		} else {
			eval(l, r, k);
			set(a, b, x, k*2+1, l, (l+r) / 2);
			set(a, b, x, k*2+2, (l+r) / 2, r);
			renode(k);
		}
	}
	NODE get(int a, int b, int k=0, int l=0, int r=-1) {
		if (r < 0) r = n;
		eval(l, r, k);
		if (b <= l || r <= a) {
			return UNITY_NODE;
		} else if (a <= l && r <= b) {
			return node[k];
		} else {
			NODE t1 = get(a, b, 2*k+1, l, (l+r) / 2);
			NODE t2 = get(a, b, 2*k+2, (l+r) / 2, r);
			renode(k);
			return merge(t1, t2);
		}
	}
};

int main(){
	int n, q;
	cin >> n >> q;
	LazySegTree<long long, long long, 0, LLONG_MAX> L(n);
	while (q--) {
		int a, s, t, x;
		cin >> a >> s >> t;
		if (a == 0) {
			cin >> x;
			L.set(s, t+1, x);
		} else {
			cout << L.get(s, t+1) << endl;
		}
	}
}