Problem: 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

Solution (in CPP):

Solution:
// AOJ DSL_2_F Range Update  and Sum
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iostream>
#include <tuple>
#include <vector>
using namespace std;
typedef long long ll;

struct Seg {
  ll vv(ll value1, ll value2) { return min(value1, value2); } // min
  ll pp(ll oldpending, ll newpending) {                       // add
    return oldpending + newpending;
  }
  // add
  ll vp(int i, ll oldvalue, ll newpending) { return oldvalue + newpending; }

  vector<ll> A;
  vector<bool> flag;
  vector<ll> pending;
  int n;

  // Endpoints returns the (closed) endpoints of the interval owned by the
  // node with array index `i`
  pair<int, int> Endpoints(int i) {
    int depth = static_cast<int>(floor(log2(i)));
    // 2^d nodes with depth d
    int per_node_in_row = n >> depth;
    int l = 1 + (i - (1 << depth)) * per_node_in_row;
    int r = l + per_node_in_row;
    return {l, r};
  }

  // ContainedIn returns whether the node with array index `i`'s interval
  // is contained in the interval [s, t)
  bool ContainedIn(int i, int s, int t) {
    int l, r;
    tie(l, r) = Endpoints(i);
    return (s <= l and t >= r);
  }

  // Intersects returns whether the node with array index `i`'s interval
  // intersects with the interval [s, t)
  bool Intersects(int i, int s, int t) {
    if (s == t) // empty
      return false;
    int l, r;
    tie(l, r) = Endpoints(i);
    return (l >= s and l < t) or (s >= l and s < r);
  }

  void Propagate(int i) {
    if (!flag[i])
      return;
    flag[i] = false;
    A[i] = vp(i, A[i], pending[i]);
    if (i < n) { // internal node
      if (flag[2 * i]) {
        pending[2 * i] = pp(pending[2 * i], pending[i]);
      } else {
        pending[2 * i] = pending[i];
        flag[2 * i] = true;
      }
      if (flag[2 * i + 1]) {
        pending[2 * i + 1] = pp(pending[2 * i + 1], pending[i]);
      } else {
        pending[2 * i + 1] = pending[i];
        flag[2 * i + 1] = true;
      }
    }
  }

  ll Get(int i, int s, int t) { // open interval [s, t)
    Propagate(i);
    if (ContainedIn(i, s, t))
      return A[i];
    if (Intersects(2 * i, s, t) and Intersects(2 * i + 1, s, t))
      return vv(Get(2 * i, s, t), Get(2 * i + 1, s, t));
    if (Intersects(2 * i, s, t))
      return Get(2 * i, s, t);
    if (Intersects(2 * i + 1, s, t))
      return Get(2 * i + 1, s, t);
  }

  void Modify(int i, int s, int t, ll x) {
    Propagate(i);
    if (ContainedIn(i, s, t)) {
      if (flag[i]) {
        pending[i] = pp(pending[i], x);
      } else {
        pending[i] = x;
        flag[i] = true;
      }
    } else if (i < n) { // internal node
      if (Intersects(2 * i, s, t))
        Modify(2 * i, s, t, x);
      if (Intersects(2 * i + 1, s, t))
        Modify(2 * i + 1, s, t, x);
      Propagate(2 * i);
      Propagate(2 * i + 1);
      A[i] = vv(A[2 * i], A[2 * i + 1]);
    }
  }

  Seg(int n, ll default_value)
      : n(n), pending(2 * n), A(2 * n, default_value), flag(2 * n) {
    for (int i = n - 1; i > 0; --i)
      A[i] = vv(A[2 * i], A[2 * i + 1]);
  }
};

int main() {
  // interface: 0-indexing, closed intervals
  // internal: 1-indexing, open intervals
  int n, q;
  ll x;
  cin >> n >> q;
  Seg seg(1 << static_cast<int>(ceil(log2(n))), 0);
  for (int c, s, t, i; cin >> c;) {
    if (c == 0) { // add(s,t,x): each i=s,..,t set a[i]+=x
      cin >> s >> t >> x;
      seg.Modify(1, s + 1, t + 2, x);
    }
    if (c == 1) { // get(s,t): output sum(a[s],...,a[t])
      cin >> s >> t;
      cout << seg.Get(1, s + 1, t + 2) << endl;
    }
  }
}