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 <vector>
#include <climits>
#include <functional>

template<typename T>
struct segment_tree {
    long long N; // 木の頂点数
    long long M; // 葉の数
    std::vector<T> V; // セグメント木　1-indexed
	std::vector<T> W; // 遅延配列　1-indexed
	std::vector<bool> flag; // true : W[i] の子孫に更新していない遅延配列が存在
    std::function<T(T, T)> op1; // 二項演算
	std::function<T(T, T, T)> op2; // 遅延伝播用の二項演算
	std::function<T(T, T)> op3; // 遅延配列更新用の二項演算
    T id1; // 単位元
	T id2; // 遅延伝播用の単位元

    // ===============================================================

    segment_tree(
		std::vector<T>& a,
		std::function<T(T, T)> f,
		std::function<T(T, T, T)> g,
		std::function<T(T, T)> h,
		T t1, T t2
	) : op1(f), op2(g), op3(h), id1(t1), id2(t2) {
        M = 1;
        while (M < a.size()) M *= 2;
        N = 2 * M;
        V.resize(N, id1); W.resize(N, id2); flag.resize(N, false);
        for (long long i = 0; i < a.size(); i++) V[M + i] = a[i];
        for (long long i = M - 1; i > 0; i--) {
            V[i] = op1(V[2 * i], V[2 * i + 1]);
        }
    }

    segment_tree() {}

    // ===============================================================

    void init(
		std::vector<T>& a,
		std::function<T(T, T)> f,
		std::function<T(T, T, T)> g,
		std::function<T(T, T)> h,
		T t1, T t2
	) {
        op1 = f; op2 = g; op3 = h; id1 = t1; id2 = t2;
		M = 1;
        while (M < a.size()) M *= 2;
        N = 2 * M;
        V.resize(N, id1); W.resize(N, id2); flag.resize(N, false);
        for (long long i = 0; i < a.size(); i++) V[M + i] = a[i];
        for (long long i = M - 1; i > 0; i--) {
            V[i] = op1(V[2 * i], V[2 * i + 1]);
        }
    }

	void laze_eval(long long cur_node, long long width) {
		if (W[cur_node] != id2) {
			V[cur_node] = op2(V[cur_node], W[cur_node], width);
			if (width > 1) {
				W[cur_node * 2] = op3(W[cur_node * 2], W[cur_node]);
				W[cur_node * 2 + 1] = op3(W[cur_node * 2 + 1], W[cur_node]);
			}
			W[cur_node] = id2;
		}
	}

	void range_update(
		long long l, long long r, T x,
		long long cur_node = 1,
		long long cur_left = 0, long long cur_right = -1
	) {
		if (cur_right == -1) cur_right = M;
		long long width = cur_right - cur_left;
		if (cur_right <= l || r <= cur_left) return;
		if (l <= cur_left && cur_right <= r) {
			W[cur_node] = op3(W[cur_node], x);
		}
		else {
			laze_eval(cur_node, width);
			flag[cur_node] = true;
			long long mid = (cur_left + cur_right) / 2;
			range_update(l, r, x, cur_node * 2, cur_left, mid);
			range_update(l, r, x, cur_node * 2 + 1, mid, cur_right);
			V[cur_node] = op1(V[cur_node * 2], V[cur_node * 2 + 1]);
		}
	}

	T range_fold(
		long long l, long long r,
		long long cur_node = 1,
		long long cur_left = 0, long long cur_right = -1
	) {
		if (cur_right == -1) cur_right = M;
		long long width = cur_right - cur_left;
		if (cur_right <= l || r <= cur_left) return id1;
		laze_eval(cur_node, width);
		if (width == 1) {
			flag[cur_node] = false;
			return V[cur_node];
		}
		long long mid = (cur_left + cur_right) / 2;
		if (l <= cur_left && cur_right <= r && !flag[cur_node]) {
			return V[cur_node];
		}
		else if (l <= cur_left && cur_right <= r) {
			flag[cur_node] = false;
			range_fold(cur_left, mid);
			range_fold(mid, cur_right);
			return V[cur_node] = op1(V[cur_node * 2], V[cur_node * 2 + 1]);
		}
		return op1(
			range_fold(l, r, cur_node * 2, cur_left, mid),
			range_fold(l, r, cur_node * 2 + 1, mid, cur_right)
		);
	}
};

int main() {
	long long n, q;
	std::cin >> n >> q;
	std::vector<long long> a(n, 0);

	auto f = [] (long long x, long long y) {return x + y;};
	auto g = [] (long long x, long long y, long long z) {return y * z;};
	auto h = [] (long long x, long long y) {return y;};
	segment_tree<long long> sg(a, f, g, h, 0, LLONG_MAX);

	while (q--) {
		long long z, s, t;
		std::cin >> z >> s >> t;
		if (z == 0) {
			long long x;
			std::cin >> x;
			sg.range_update(s, t + 1, x);
		}
		else std::cout << sg.range_fold(s, t + 1) << '\n';
	}
}