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"

class LazySegmentTree
{
    int n;
    using T1 = long long;
    using T2 = long long;
    T1 id1 = 0;
    T2 id2 = -INT_MAX;
    std::vector<T1> node; // sum
    std::vector<T2> lazy; // update

    // 遅延評価
    void eval(int k, int l, int r)
    {
        // 遅延配列が空なら終了
        if (lazy[k] == id2)
            return;
        // 遅延配列を適用
        node[k] = lazy[k];
        if (r - l > 1)
        {
            lazy[2 * k + 1] = lazy[k] / 2;
            lazy[2 * k + 2] = lazy[k] / 2;
        }
        // 遅延配列初期化
        lazy[k] = id2;
    }

  public:
    LazySegmentTree(int _n)
    {
        int sz = _n;
        n = 1;
        while (n < sz)
            n *= 2;
        // 配列初期化
        node.resize(2 * n - 1, id1);
        lazy.resize(2 * n - 1, id2);
    }
    // 半開区間 [a, b) に対して値 val を反映させる
    void update(int a, int b, T2 val, int l = 0, int r = -1, int k = 0)
    {
        if (r < 0)
            r = n;
        // ノード k で遅延評価
        eval(k, l, r);
        if (b <= l || r <= a)
            return;
        // 区間が被覆されている場合
        if (a <= l && r <= b)
        {
            // 遅延配列更新, 評価
            lazy[k] = (r - l) * val;
            eval(k, l, r);
        }
        else
        {
            // 子ノードの値を評価し, 更新
            int mid = (l + r) / 2;
            update(a, b, val, l, mid, 2 * k + 1);
            update(a, b, val, mid, r, 2 * k + 2);
            node[k] = node[2 * k + 1] + node[2 * k + 2];
        }
    }

    // 半開区間 [a, b) に対してクエリを投げる
    T1 query(int a, int b, int l = 0, int r = -1, int k = 0)
    {
        if (r < 0)
            r = n;
        eval(k, l, r);
        // 範囲外なら単位元返す
        if (b <= l || r <= a)
            return id1;
        if (a <= l && r <= b)
            return node[k];
        int mid = (l + r) / 2;
        T1 vl = query(a, b, l, mid, 2 * k + 1);
        T1 vr = query(a, b, mid, r, 2 * k + 2);
        return vl + vr;
    }
};

using namespace std;

void solve_dsl_2_i()
{
    int n, q;
    cin >> n >> q;
    LazySegmentTree lst(n);
    while (q--)
    {
        int type;
        cin >> type;
        if (type == 0)
        {
            int s, t, x;
            cin >> s >> t >> x;
            t++;
            lst.update(s, t, x);
        }
        else
        {
            int s, t;
            cin >> s >> t;
            t++;
            cout << lst.query(s, t) << endl;
        }
    }
}

int main()
{
    solve_dsl_2_i();
}