RSQ and RUQ

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

inputFormat

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)$.

outputFormat

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

样例

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

-5
1
6
8

</p>