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 <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n)-1; i >= 0; i--)
constexpr char newl = '\n';

constexpr int None = 1 << 30;

constexpr int h = 17;
constexpr int MaxN = 1 << h;
int n, q;

int dat[MaxN*2], laz[MaxN*2];

void apply(int p, int x, int i) {
  dat[p] = x << i;
  laz[p] = x;
}

void flush(int p) {
  repr(i, h) {
    int q = p >> i+1;
    if (laz[q] != None) {
      apply(q<<1, laz[q], i);
      apply(q<<1|1, laz[q], i);
      laz[q] = None;
    }
  }
}

void build(int p) {
  rep(i, h) {
    int q = p >> i+1;
    dat[q] = laz[q] != None ? laz[q] << i+1 : dat[q<<1] + dat[q<<1|1];
  }
}

int main() {
  cin >> n >> q;
  fill(laz, laz+MaxN*2, None);
  rep(_, q) {
    int c, s, t; cin >> c >> s >> t;
    if (c == 0) {
      int x; cin >> x;
      flush(s += MaxN); flush(t += MaxN);
      int s0 = s, t0 = t, i;
      for (i = 0, t++; s < t; s >>= 1, t >>= 1, i++) {
        if (s&1) apply(s++, x, i);
        if (t&1) apply(--t, x, i);
      }
      build(s0); build(t0);
    } else {
      flush(s += MaxN); flush(t += MaxN);
      int res = 0;
      for (t++; s < t; s >>= 1, t >>= 1) {
        if (s&1) res += dat[s++];
        if (t&1) res += dat[--t];
      }
      cout << res << newl;
    }
  }
}