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;

struct RSQ {
	using type = int;
	static type id() { return 0; }
	static type op(const type& l, const type & r) { return l + r; }
};

struct seg_node {
	using M = RSQ;
	using T = typename M::type;
	using U = int;

	T val;

private:
	int size;
	bool flag;
	U lazy;

public:
	seg_node() : val(), size(0), flag(false) {}
	void init_leaf(const T& v) {
		val = v;
		size = 1;
	}
	void init_non_leaf(const seg_node& l, const seg_node& r) {
		val = M::op(l.val, r.val);
		size = l.size + r.size;
	}
	void update(U v) {
		val = v * size;
		lazy = v;
		flag = true;
	}
	void push(seg_node& l, seg_node& r) {
		if (!flag) return;
		l.update(lazy);
		r.update(lazy);
		flag = false;
	}
	bool is_updated() const {
		return flag;
	}

};

class lazy_segment_tree {
	using M = typename seg_node::M;
	using T = typename seg_node::T;
	using U = typename seg_node::U;
	const int h, n;
	vector<seg_node> data;
	void push(int node) {
		data[node].push(data[node << 1], data[(node << 1) | 1]);
	}
	void update(int node) {
		data[node].val = M::op(data[node << 1].val, data[(node << 1) | 1].val);
	}
public:
	lazy_segment_tree(int n_)
		: h(ceil(log2(n_))), n(1 << h), data(n * 2) {}
	lazy_segment_tree(int n_, T v1)
		: h(ceil(log2(n_))), n(1 << h), data(n * 2) {
		for (int i = 0; i < n_; i++)
			data[i + n].init_leaf(v1);
		for (int i = n - 1; i >= 1; i--)
			data[i].init_non_leaf(data[i << 1], data[(i << 1) | 1]);
	}
	lazy_segment_tree(const vector<T>& data_)
		: h(ceil(log2(data_.size()))), n(1 << h), data(n * 2) {
		for (int i = 0; i < (int)data_.size(); i++)
			data[i + n].init_leaf(data_[i]);
		for (int i = n - 1; i >= 1; i--)
			data[i].init_non_leaf(data[i << 1], data[(i << 1) | 1]);
	}
	void update(int l, int r, U val) {
		l += n, r += n;
		for (int i = h; i > 0; i--) push(l >> i), push(r >> i);
		int tl = l, tr = r;
		r++;
		while (l < r) {
			if (l & 1) data[l++].update(val);
			if (r & 1) data[--r].update(val);
			l >>= 1; r >>= 1;
		}
		while (tl >>= 1, tr >>= 1, tl) {
			if (!data[tl].is_updated()) update(tl);
			if (!data[tr].is_updated()) update(tr);
		}
	}
	T find(int l, int r) {
		l += n, r += n;
		for (int i = h; i > 0; i--) push(l >> i), push(r >> i);
		r++;
		T res1 = M::id(), res2 = M::id();
		while (l < r) {
			if (l & 1) res1 = M::op(res1, data[l++].val);
			if (r & 1) res2 = M::op(data[--r].val, res2);
			l >>= 1; r >>= 1;
		}
		return M::op(res1, res2);
	}
};

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	int n, q;
	cin >> n >> q;
	lazy_segment_tree st(n, 0);
	while (q--) {
		int com;
		cin >> com;
		if (com == 0) {
			int s, t, x;
			cin >> s >> t >> x;
			st.update(s, t, x);
		}
		else {
			int s, t;
			cin >> s >> t;
			printf("%d\n", st.find(s, t));
		}
	}
	return 0;
}