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:
#include <cstdio>
#include <functional>
#include <vector>

using namespace std;

#define int long long
#define dotimes(i, n) for (int i = 0, i##max__ = (n); i < i##max__; i++)
#define whole(x, f, ...) ([&](decltype((x)) c) { return (f)(begin(c), end(c), ## __VA_ARGS__); })(x)

int rint() {
  int x;
  scanf("%lld", &x);
  return x;
}

void wint(int x) {
  printf("%lld\n", x);
}

template<typename T> int size(T const& c) { return static_cast<int>(c.size()); }
template <typename T> bool maxs(T& a, T const& b) { return a < b ? a = b, true : false; }
template <typename T> bool mins(T& a, T const& b) { return a > b ? a = b, true : false; }
inline int lg(int x) { return 63 - __builtin_clzll(static_cast<unsigned int>(x)); }

class segment_tree {
  vector<pair<int, int>> xs;
public:
  segment_tree(int n) : xs(1 << (lg(2 * n - 1) + 1)) {}
  void update(const int i, const int j, int x) {
    function<void(int, int, int)> rec;
    rec =
      [&](int k, int a, int b) {
        if (i <= a && b <= j) {
          xs[k].first += x;
          xs[k].second += x;
        } else {
          int c = a + (b - a) / 2;
          if (xs[k].second != 0) {
            xs[2*k].first += xs[k].second;
            xs[2*k].second += xs[k].second;
            xs[2*k+1].first += xs[k].second;
            xs[2*k+1].second += xs[k].second;
            xs[k].second = 0;
          }
          if (j <= c)
            rec(2*k, a, c);
          else if (c <= i)
            rec(2*k+1, c, b);
          else {
            rec(2*k, a, c);
            rec(2*k+1, c, b);
          }
          xs[k].first = min(xs[2*k].first, xs[2*k+1].first);
        }
      };
    rec(1, 0, ::size(xs)/2);
  }
  int query(const int i, const int j) {
    function<int(int, int, int)> rec;
    rec =
      [&](int k, int a, int b) {
        if (i <= a && b <= j)
          return xs[k].first;
        int c = a + (b - a) / 2;
        return xs[k].second + (j <= c ? rec(2*k, a, c) : c <= i ? rec(2*k+1, c, b) : min(rec(2*k, a, c), rec(2*k+1, c, b)));
      };
    return rec(1, 0, ::size(xs)/2);
  }
};

signed main() {
  const int n = rint();
  segment_tree st(n);
  const int q = rint();
  dotimes(i, q)
    if (rint()) {
      int s = rint();
      int t = rint();
      wint(st.query(s, t+1));
    } else {
      int s = rint();
      int t = rint();
      int x = rint();
      st.update(s, t+1, x);
    }
  return 0;
}