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 <iostream>
#include <vector>
#include <limits>
#include <algorithm>
#include <iomanip>

using namespace std;

template<class T>
class StarrySkyTree {
    private:
        int N;
        const T MAX;
        const T ZERO;
        std::vector<T> dat, lazy;
    public:
        StarrySkyTree(int n) : MAX(std::numeric_limits<T>::max()), ZERO(static_cast<T>(0)) {
            N = 1;
            while (N < n) N *= 2;
            dat.assign(2*N, MAX);
            lazy.assign(2*N, ZERO);
        }
        // a is 0-indexed
        void set(int a, const T v) {
            dat.at(a+N) = v;
        }
        void build() {
            for (int i=N-1; i>0; --i) dat.at(i) = std::min(dat.at(2*i), dat.at(2*i+1));
        }
        void eval(int k, int l, int r) {
            if (lazy.at(k) == ZERO) return;

            dat.at(k) += lazy.at(k);
            if (r - l > 1) {
                lazy.at(2*k) += lazy.at(k);
                lazy.at(2*k+1) += lazy.at(k);
            }
            lazy.at(k) = ZERO;
        }
        // add v to [a, b)
        // a and b are 0-indexed
        void add(int a, int b, const T v) {
            return add (a, b, v, 1, 0, N);
        }
        void add(int a, int b, const T v, int k, int l, int r) {
            eval(k, l, r);

            if (b <= l || r <= a) return;
            if (a <= l && r <= b) {
                lazy.at(k) += v;
                eval(k, l, r);
            } else {
                add(a, b, v, 2*k, l, (l+r)/2);
                add(a, b, v, 2*k+1, (l+r)/2, r);
                dat.at(k) = std::min(dat.at(2*k), dat.at(2*k+1));
            }
        }
        // get min of [a, b)
        // a and b are 0-indexed
        T get(int a, int b) {
            return get(a, b, 1, 0, N);
        }
        T get(int a, int b, int k, int l, int r) {
            eval(k, l, r);

            if (b <= l || r <= a) return MAX;
            if (a <= l && r <= b) return dat.at(k);
            T vleft = get(a, b, 2*k, l, (l+r)/2);
            T vright = get(a, b, 2*k+1, (l+r)/2, r);
            return std::min(vleft, vright);
        }
};

void solve() {
    int n, q;
    cin >> n >> q;

    StarrySkyTree<int> sst(n);
    for (int i=0; i<n; ++i) sst.set(i, 0);
    sst.build();

    for (int i=0; i<q; ++i) {
        int a;
        cin >> a;
        if (a == 0) {
            int s, t, x;
            cin >> s >> t >> x;
            sst.add(s, t+1, x);
        } else {
            int s, t;
            cin >> s >> t;
            cout << sst.get(s, t+1) << '\n';
        }
    }
}

int main() {

    solve();

    return 0;
}