RMQ and RAQ

Write a program which manipulates a sequence $A$ = {$a_0, a_1, ..., a_{n-1}$} with the following operations:

• $add(s, t, x)$ : add $x$ to $a_s, a_{s+1}, ..., a_t$.
• $find(s, t)$ : report the minimum value in $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 $add(s, t, x)$ and '1' denotes $find(s, t)$.

Output

For each $find$ query, print the minimum value.

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

-2 0 1 -1

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 $add(s, t, x)$ and '1' denotes $find(s, t)$.

outputFormat

Output

For each $find$ query, print the minimum value.

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

-2 0 1 -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

-2
0
1
-1

</p>