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 <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.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 data[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){
		data[node_id] = new_value;
	}else{
		if(data[node_id] != -BIG_NUM){
			data[2*node_id+1] = data[node_id];
			data[2*node_id+2] = data[node_id];
			data[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(data[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)*data[node_id];
		}
	}
}


int main(){

	int first_N,num_query;
	scanf("%d %d",&first_N,&num_query);

	init(first_N);

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

	int command,left,right,value;

	for(int loop = 0; loop < num_query; loop++){
		scanf("%d",&command);

		if(command == 0){ //update
			scanf("%d %d %d",&left,&right,&value);
			update(left,right,value,0,0,N-1);
		}else{
			scanf("%d %d",&left,&right);
			printf("%d\n",getSum(left,right,0,0,N-1));
		}
	}

	return 0;
}