時間制限 : sec, メモリ制限 : KB
English / Japanese  

RSQ and RUQ

数列 $A$ = {$a_0, a_1, ..., a_{n-1}$} に対し、次の2つの操作を行うプログラムを作成せよ。

  • $update(s, t, x) : a_s, a_{s+1}, ..., a_t$ を$x$ に変更する。
  • $getSum(s, t) : a_s, a_{s+1}, ..., a_t$ の合計値を出力する。

ただし、$a_i ( i = 0, 1, ..., n-1 )$ は、0で初期化されているものとする。

Input

$n$ $q$
$query_1$
$query_2$
:
$query_q$

1行目に $A$ の要素数 $n$ , クエリの数 $q$ が与えられる。続く $q$ 行に、 $i$ 番目のクエリ $query_i$ が与えられる。 $query_i$ は以下のいずれかの形式で与えられる。

0 $s$ $t$ $x$

または

1 $s$ $t$

各クエリの最初の数字は、クエリの種類を示し、'0'が $update(s, t, x)$ , '1'が $getSum(s, t)$ を表す。

Output

各 $getSum$ クエリについて、合計値を1行に出力せよ。

Constraints

  • $1 ≤ n ≤ 100000$
  • $1 ≤ q ≤ 100000$
  • $0 ≤ s ≤ t < n$
  • $-1000 ≤ x ≤ 1000$

Sample Input 1

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

Sample Output 1

-5
1
6
8