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

RMQ and RAQ

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

  • $add(s, t, x)$ : $a_s, a_{s+1}, ..., a_t$ に $x$ を加算する。
  • $find(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'が $add(s, t, x)$ , '1'が $find(s, t)$を表す。

Output

各 $find$ クエリについて、最小値を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

-2
0
1
-1