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 JAVA):

Solution:
import java.io.InputStream;
import java.io.PrintStream;
import java.util.Arrays;
import java.util.Scanner;

class LazySegmentTree {

	int[] nodes;
	int[] lazy;
	boolean[] isLazy;

	int n;
	int e; // 単位元

	public LazySegmentTree(int size) {
		n = 1;
		while (n < size) {
			n *= 2;
		}

		nodes = new int[2 * n - 1];
		lazy = new int[2 * n - 1];
		isLazy = new boolean[2 * n - 1];

		e = 0; // 単位元は0
	}

	private void eval(int k, int l, int r) {
		if (isLazy[k]) {

			// 葉でないなら
			if (r - l > 1) {
				// 子に伝搬
				lazy[2 * k + 1] = lazy[k] / 2;
				lazy[2 * k + 2] = lazy[k] / 2;

				isLazy[2 * k + 1] = true;
				isLazy[2 * k + 2] = true;
			}

			nodes[k] = lazy[k];

			lazy[k] = 0;
			isLazy[k] = false;
		}
	}

	private void update(int a, int b, int val, int k, int l, int r) {
		eval(k, l, r);
		if (a >= r || b <= l) {
			return;
		}

		if (a <= l && r <= b) {
			lazy[k] = (r - l) * val;
			isLazy[k] = true;
			eval(k, l, r);
			return;
		}

		update(a, b, val, 2 * k + 1, l, (l + r) / 2);
		update(a, b, val, 2 * k + 2, (l + r) / 2, r);

		nodes[k] = nodes[2 * k + 1] + nodes[2 * k + 2];

	}

	private int getSum(int a, int b, int k, int l, int r) {
		if (a >= r || b <= l) {
			return e;
		}

		eval(k, l, r);
		if (a <= l && r <= b) {
			return nodes[k];
		}

		int vl = getSum(a, b, 2 * k + 1, l, (l + r) / 2);
		int vr = getSum(a, b, 2 * k + 2, (l + r) / 2, r);

		return vl + vr;

	}

	public void update(int a, int b, int val) {
		update(a, b, val, 0, 0, n);
	}

	public int getSum(int a, int b) {
		return getSum(a, b, 0, 0, n);
	}

	public String debug() {
		StringBuffer buf = new StringBuffer();
		
		for(int s=0,n=1;s<nodes.length;s+=n,n*=2) {
			buf.append(_debug(nodes,s,s+n, this.n));
			buf.append("\n");
		}
		
		buf.append("--\n");
		
		for(int s=0,n=1;s<lazy.length;s+=n,n*=2) {
			buf.append(_debug(lazy,s,s+n, this.n));
			buf.append("\n");
		}
		return buf.toString();
	}
	
	private String _debug(int[] a, int s, int e, int x) {
		StringBuffer buf = new StringBuffer();
		for(int i=s;i<e;i++) {
			buf.append(a[i]);
			for(int j=0;j<(2*x)/(e-s) -1;j++) 
				buf.append(" ");
		}
		return buf.toString();
	}
	

	
}

public class Main {
	InputStream in = System.in;
	PrintStream out = System.out;

	public void _main(String[] args) {
		Scanner sc = new Scanner(in);

		int n = sc.nextInt();
		int q = sc.nextInt();

		LazySegmentTree seg = new LazySegmentTree(n);

		for (int i = 0; i < q; i++) {
			int c = sc.nextInt();
			if (c == 0) {
				int s = sc.nextInt();
				int t = sc.nextInt() + 1;
				int x = sc.nextInt();

				seg.update(s, t, x);

			} else {
				int s = sc.nextInt();
				int t = sc.nextInt() + 1;

				out.println(seg.getSum(s, t));
			}
		}

		sc.close();

	}

	public static void main(String[] args) {
		new Main()._main(args);
	}
}