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:
//https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_I
#include <bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;
#define NUM 100000

int N = 1;
int value[4*NUM];

void init(int first_N){
	while(N < first_N)N *= 2;
}

void update(int update_left,int update_right,int new_value,int node_id,int node_left,int node_right){
	if(update_right < node_left || update_left > node_right)return;
	else if(update_left <= node_left && update_right >= node_right){
		value[node_id] = new_value;
	}else{
		if(value[node_id] != -BIG_NUM){
			value[2*node_id+1] = value[node_id];
			value[2*node_id+2] = value[node_id];
			value[node_id] = -BIG_NUM;
		}
		update(update_left,update_right,new_value,2*node_id+1,node_left,(node_left+node_right)/2);
		update(update_left,update_right,new_value,2*node_id+2,(node_left+node_right)/2+1,node_right);
	}
}

int getSum(int search_left,int search_right,int node_id,int node_left,int node_right){
	if(search_right < node_left || search_left > node_right){
		return 0;
	}else{
		if(value[node_id] == -BIG_NUM){
			int left = getSum(search_left,search_right,2*node_id+1,node_left,(node_left+node_right)/2);
			int right = getSum(search_left,search_right,2*node_id+2,(node_left+node_right)/2+1,node_right);
			return left+right;
		}else{
			return (min(search_right,node_right)-max(search_left,node_left)+1)*value[node_id];
		}
	}
}


int main(){

	int n,q; cin >> n >> q;

	init(n);

	for(int i = 0; i <= 2*N-2; i++) value[i] = 0;

	int command,left,right,value;

	for(int loop = 0; loop < q; loop++){
		cin >> command;

		if(command == 0){ //update
			cin >> left >> right >> value;
			update(left,right,value,0,0,N-1);
		}else{
			cin >> left >> right;
			cout << getSum(left,right,0,0,N-1) << endl;
		}
	}
	return 0;
}