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:
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
using namespace std;
#define Ma_PI 3.141592653589793
#define eps 0.00000001
#define LONG_INF 3000000000000000000
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007
#define MOD 998244353
#define REP(i,n) for(long long i = 0;i < n;++i)    
#define seg_size 524288
#define int long long
int seg_tree[seg_size*4];
int seg_sub[seg_size*4];
int seg_set(int now,int cnt){
    if(seg_sub[now*2] != -10000){
        seg_tree[now*2] = seg_sub[now*2] * cnt;
        seg_sub[now*2*2] = seg_sub[now*2];
        seg_sub[now*2*2+1] = seg_sub[now*2];
        seg_sub[now*2] = -10000;
    }
    if(seg_sub[now*2+1] != -10000){
        seg_tree[(now*2+1)] = seg_sub[(now*2+1)] * cnt;
        seg_sub[(now*2+1)*2] = seg_sub[(now*2+1)];
        seg_sub[(now*2+1)*2+1] = seg_sub[(now*2+1)];
        seg_sub[(now*2+1)] = -10000;
    }
    seg_tree[now] = seg_tree[now*2] + seg_tree[now*2+1];
    if(now > 1){
        seg_set(now/2,cnt*2);
    }
    return 0;
}
int seg_find(int now,int n_l,int n_r,int w_l,int w_r){
    if(seg_sub[now] != -10000){
        seg_tree[now] = seg_sub[now] * (n_r - n_l);
        seg_sub[now*2] = seg_sub[now];
        seg_sub[now*2+1] = seg_sub[now];
        seg_sub[now] = -10000;
    }
    if(w_l <= n_l&&n_r <= w_r) return seg_tree[now];
    if(n_r <= w_l||w_r <= n_l) return 0;
    return seg_find(now*2,n_l,(n_l+n_r)/2,w_l,w_r)+seg_find(now*2+1,(n_l+n_r)/2,n_r,w_l,w_r);
}
int seg_add(int now,int n_l,int n_r,int w_l,int w_r,int setting){
    if(seg_sub[now] != -10000){
        seg_tree[now] = seg_sub[now] * (n_r - n_l);
        seg_sub[now*2] = seg_sub[now];
        seg_sub[now*2+1] = seg_sub[now];
        seg_sub[now] = -10000;
    }
    if(w_l <= n_l&&n_r <= w_r){
        seg_sub[now] = setting;
        seg_set(now/2,n_r - n_l);
        return seg_tree[now];
    }
    if(n_r <= w_l||w_r <= n_l) return (1LL << 31LL) - 1LL;
    return min(seg_add(now*2,n_l,(n_l+n_r)/2,w_l,w_r,setting),seg_add(now*2+1,(n_l+n_r)/2,n_r,w_l,w_r,setting));
}
#undef int
int main(){
#define int long long
    int n,m;
    cin >> n >> m;
    REP(i,seg_size*4){
        seg_tree[i] = 0;
        seg_sub[i] = -10000;
    }
    REP(i,m){
        int a;
        cin >> a;
        if(a == 0){
            int b,c,d;
            cin >> b >> c >> d;
            seg_add(1,0,seg_size,b,c+1,d);
        }else{
            int b,c;
            cin >> b >> c;
            cout << seg_find(1,0,seg_size,b,c+1) << endl;
        }
    }
}