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:
/**
 *    author:  math2do
 *    created: 28.02.2020 20:21:13
**/

#include <bits/stdc++.h>

using namespace std;

class segtree {
 public:
  struct node {
    // don't forget to set default value (used for leaves)
    // not necessarily neutral element!

    int val = 0;
    int sum = 0;
    bool mark = false;

    void apply(int l, int h, int v) {
      val = v;
      sum = (h - l + 1) * v;
      mark = true;
    }
  };
 
  node unite(const node &a, const node &b) const {
    node res;
    res.sum = a.sum + b.sum;
    return res;
  }
 
  inline void push(int i, int l, int h) {
    int m = (l + h) >> 1;
    // push from i into left child and right child
    if (tree[i].mark) {
      tree[i << 1].apply(l, m, tree[i].val);
      tree[(i << 1) + 1].apply(m + 1, h, tree[i].val);
      tree[i].mark = false;
    }
  }
 
  inline void pull(int i) {
    tree[i] = unite(tree[i << 1], tree[(i << 1) + 1]);
  }
 
  int n;
  vector<node> tree;
 
  void build(int i, int l, int h) {
    if (l == h) {
      return;
    }
    int m = (l + h) >> 1;
    build(i << 1, l, m);
    build((i << 1) + 1, m + 1, h);
    pull(i);
  }
 
  template <typename M>
  void build(int i, int l, int h, const vector<M> &v) {
    if (l == h) {
      tree[i].apply(l, h, v[l]);
      return;
    }
    int m = (l + h) >> 1;
    build(i << 1, l, m, v);
    build((i << 1) + 1, m + 1, h, v);
    pull(i);
  }
 
  node get(int i, int l, int h, int ql, int qh) {
    if (ql <= l && h <= qh) {
      return tree[i];
    }
    int m = (l + h) >> 1;
    push(i, l, h);
    node res{};
    if (qh <= m) {
      res = get(i << 1, l, m, ql, qh);
    } else {
      if (ql > m) {
        res = get((i << 1) + 1, m + 1, h, ql, qh);
      } else {
        res = unite(get(i << 1, l, m, ql, qh), get((i << 1) + 1, m + 1, h, ql, qh));
      }
    }
    pull(i);
    return res;
  }
 
  template <typename... M>
  void modify(int i, int l, int h, int ql, int qh, const M&... v) {
    if (ql <= l && h <= qh) {
      tree[i].apply(l, h, v...);
      return;
    }
    int m = (l + h) >> 1;
    push(i, l, h);
    if (ql <= m) {
      modify(i << 1, l, m, ql, qh, v...);
    }
    if (qh > m) {
      modify((i << 1) + 1, m + 1, h, ql, qh, v...);
    }
    pull(i);
  }
 
  int find_first_knowingly(int i, int l, int h, const function<bool(const node&)> &f) {
    if (l == h) {
      return l;
    }
    push(i, l, h);
    int m = (l + h) >> 1;
    int res;
    if (f(tree[i << 1])) {
      res = find_first_knowingly(i << 1, l, m, f);
    } else {
      res = find_first_knowingly((i << 1) + 1, m + 1, h, f);
    }
    pull(i);
    return res;
  }
 
  int find_first(int i, int l, int h, int ql, int qh, const function<bool(const node&)> &f) {
    if (ql <= l && h <= qh) {
      if (!f(tree[i])) {
        return -1;
      }
      return find_first_knowingly(i, l, h, f);
    }
    push(i, l, h);
    int m = (l + h) >> 1;
    int res = -1;
    if (ql <= m) {
      res = find_first(i << 1, l, m, ql, qh, f);
    }
    if (qh > m && res == -1) {
      res = find_first((i << 1) + 1, m + 1, h, ql, qh, f);
    }
    pull(i);
    return res;
  }
 
  int find_last_knowingly(int i, int l, int h, const function<bool(const node&)> &f) {
    if (l == h) {
      return l;
    }
    push(i, l, h);
    int m = (l + h) >> 1;
    int res;
    if (f(tree[(i << 1) + 1])) {
      res = find_last_knowingly((i << 1) + 1, m + 1, h, f);
    } else {
      res = find_last_knowingly(i << 1, l, m, f);
    }
    pull(i);
    return res;
  }
 
  int find_last(int i, int l, int h, int ql, int qh, const function<bool(const node&)> &f) {
    if (ql <= l && h <= qh) {
      if (!f(tree[i])) {
        return -1;
      }
      return find_last_knowingly(i, l, h, f);
    }
    push(i, l, h);
    int m = (l + h) >> 1;
    int res = -1;
    if (qh > m) {
      res = find_last((i << 1) + 1, m + 1, h, ql, qh, f);
    }
    if (ql <= m && res == -1) {
      res = find_last(i << 1, l, m, ql, qh, f);
    }
    pull(i);
    return res;
  }
 
  segtree(int _n) : n(_n) {
    assert(n > 0);
    tree.resize(4 * n);
    build(1, 0, n - 1);
  }
 
  template <typename M>
  segtree(const vector<M> &v) {
    n = v.size();
    assert(n > 0);
    tree.resize(4 * n);
    build(1, 0, n - 1, v);
  }
 
  node get(int ql, int qh) {
    assert(0 <= ql && ql <= qh && qh <= n - 1);
    return get(1, 0, n - 1, ql, qh);
  }
 
  node get(int p) {
    assert(0 <= p && p <= n - 1);
    return get(1, 0, n - 1, p, p);
  }
 
  template <typename... M>
  void modify(int ql, int qh, const M&... v) {
    assert(0 <= ql && ql <= qh && qh <= n - 1);
    modify(1, 0, n - 1, ql, qh, v...);
  }
 
  // find_first and find_last call all FALSE elements
  // to the left (right) of the sought position exactly once
 
  int find_first(int ql, int qh, const function<bool(const node&)> &f) {
    assert(0 <= ql && ql <= qh && qh <= n - 1);
    return find_first(1, 0, n - 1, ql, qh, f);
  }
 
  int find_last(int ql, int qh, const function<bool(const node&)> &f) {
    assert(0 <= ql && ql <= qh && qh <= n - 1);
    return find_last(1, 0, n - 1, ql, qh, f);
  }
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  segtree st(n);
  while (q--) {
    int t;
    cin >> t;
    if (t == 0) {
      int x, y, v;
      cin >> x >> y >> v;
      st.modify(x, y, v);
    } else {
      int x, y;
      cin >> x >> y;
      auto ans = st.get(x, y);
      cout << ans.sum << '\n';
    } 
  } 
  return 0;
}