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:
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <bitset>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
#define IINF 100000000
//#define INF 300000000000000000
#define MOD 1000000007
#define mod 1000000007
#define INT_MAX_ 2147483647
#define REP(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define REPE(i, a, n) for (ll i = a; i <= (ll)(n); i++)
#define rep(i,n)for (ll i = 0; i < (ll)(n); i++)
#define Endl endl
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define PI acos(-1.0)
#define me memset
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
typedef pair<int,int>Pin;
typedef pair<ll,ll>Pll;
template<class T> using V=vector<T>;
long long GCD(long long a, long long b) {return b?GCD(b,a%b):a;}
long long LCM(long long a, long long b) {return a/GCD(a,b)*b;}
int dx[5]={-1,0,1,0,0};
int dy[5]={0,-1,0,1,0};
int ddx[8]={-1,0,1,0,1,1,-1,-1};
int ddy[8]={0,-1,0,1,1,-1,1,-1};
ll cmp1(pair<ll,ll>a,pair<ll,ll> b){
        if(a.se!=b.se)
        return a.se<b.se;
        else
        return a.fi<b.fi;
}
//----------------------------------------------------------------------
/// RSQ and RUQ
int num = 1;
vector<Pll> A;  // first: 値, second: 遅延評価値
vector<bool> lazyFlag;  // 遅延ありかどうか
const long long INF = 1LL << 60;

// ノード番号 k を遅延評価する (A.at(k).first を正しい値に)
void eval(int k, int l, int r) {
  if (lazyFlag.at(k)) {
    A.at(k).first = A.at(k).second;
    if (r - l > 1) {
      A.at(2*k+1).second = A.at(2*k+2).second = A.at(k).second / 2;
      lazyFlag.at(2*k+1) = lazyFlag.at(2*k+2) = lazyFlag.at(k);
    }
    lazyFlag.at(k) = false;
  }
}

// [a, b) の要素を x に更新
// ノード番号 k は [l, r) に対応している
void update(int a, int b, int x, int k, int l, int r) {
  eval(k, l, r);
  // [a, b) と [l, r) が交差していない
  if (r <= a || b <= l) return;
  // [a, b) が [l, r) を完全に含む
  if (a <= l && r <= b) {
    A.at(k).second = x * (r - l);
    lazyFlag.at(k) = true;
    eval(k, l, r);
  }
  else {
    update(a, b, x, 2*k+1, l, (l+r)/2);
    update(a, b, x, 2*k+2, (l+r)/2, r);
    A.at(k).first = A.at(2*k+1).first + A.at(2*k+2).first;
  }
}

// [a, b) の合計値を返す
long long getSum(int a, int b, int k, int l, int r) {
  eval(k, l, r);
  if (r <= a || b <= l) return 0;
  if (a <= l && r <= b) return A.at(k).first;
  else {
    long long c1 = getSum(a, b, 2*k+1, l, (l+r)/2);
    long long c2 = getSum(a, b, 2*k+2, (l+r)/2, r);
    return c1 + c2;
  }
}
//----------------------------------------------------------------------
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    //-------------------------------  
    //ll begin_time=clock();
    //-------------------------------
    ll n,q;cin>>n>>q;
    num = 1;
    while (num < n) num *= 2;  // 要素数は 2 のべき乗にする
    // 要素数 n のときに必要なノード数は 2*n - 1
    A = vector<Pll>(2*num - 1, make_pair(0, 0));
    lazyFlag = vector<bool>(2*num - 1, false);
    for(ll i=0;i<q;i++){
        ll co;cin>>co;
        if(co==1){
            ll x,y;cin>>x>>y;
            cout<<getSum(x,y+1,0,0,num)<<endl;
        }  
        else{
            ll x,y,z;cin>>x>>y>>z;
            update(x,y+1,z,0,0,num);
        }
    }
    //-------------------------------  
    //ll end_time=clock();cout<<"time="<<end_time-begin_time<<"ms"<<endl;
    //-------------------------------
    return 0;
}
//----------------------------------------------------------------------