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 <functional>
#include <limits>

template <class Data, class Operator>
class LazySegmentTree {
    using DataMerger = std::function<Data(Data, Data)>;
    using OperatorMerger = std::function<Operator(Operator, Operator)>;
    using Applier = std::function<Data(Data, Operator, int)>;

public:
    int length;
    std::vector<Data> dat;
    std::vector<Operator> ope;
    Data dat_id;
    Operator ope_id;
    DataMerger datm;
    OperatorMerger opem;
    Applier app;

    explicit LazySegmentTree(int N, Data dat_id, Operator ope_id, DataMerger datm, OperatorMerger opem, Applier app)
        : length(1), dat_id(dat_id), ope_id(ope_id), datm(datm), opem(opem), app(app) {
        while (length < N) length *= 2;
        dat.assign(length * 2, dat_id);
        ope.assign(length * 2, ope_id);
    }

    void eval(int nidx, int len) {
        if (ope[nidx] == ope_id) return;
        // 子に作用素を伝播
        if (nidx * 2 + 1 < length * 2) {
            ope[nidx * 2] = opem(ope[nidx * 2], ope[nidx]);
            ope[nidx * 2 + 1] = opem(ope[nidx * 2 + 1], ope[nidx]);
        }
        // 値に作用素を反映
        dat[nidx] = app(dat[nidx], ope[nidx], len);
        ope[nidx] = ope_id;
    }

    // half-open interval [ql, qr)
    Data update(int ql, int qr, Operator e) { return update(ql, qr, e, 1, 0, length); }
    Data update(int ql, int qr, Operator e, int nidx, int nl, int nr) {
        eval(nidx, nr - nl);
        if (nr <= ql || qr <= nl) return dat[nidx];
        if (ql <= nl && nr <= qr) {
            ope[nidx] = opem(ope[nidx], e);
            return app(dat[nidx], ope[nidx], nr - nl);
        }
        // 子を再帰的に更新
        Data vl = update(ql, qr, e, nidx * 2, nl, (nl + nr) / 2);
        Data vr = update(ql, qr, e, nidx * 2 + 1, (nl + nr) / 2, nr);
        // 子の更新後から値を更新
        return dat[nidx] = datm(vl, vr);
    }

    // half-open interval [ql, qr)
    Data query(int ql, int qr) { return query(ql, qr, 1, 0, length); }
    Data query(int ql, int qr, int nidx, int nl, int nr) {
        eval(nidx, nr - nl);
        if (nr <= ql || qr <= nl) return dat_id;
        if (ql <= nl && nr <= qr) return dat[nidx];
        Data vl = query(ql, qr, nidx * 2, nl, (nl + nr) / 2);
        Data vr = query(ql, qr, nidx * 2 + 1, (nl + nr) / 2, nr);
        return datm(vl, vr);
    }
};

const int INF = std::numeric_limits<int>::max();

int main() {
    int N, Q;
    std::cin >> N >> Q;
    LazySegmentTree<int, int> seg(N, INF, 0,
                                  [](int a, int b) { return std::min(a, b); },
                                  [](int e, int f) { return e + f; },
                                  [](int a, int e, int k) { return a + e; });
    seg.update(0, N, -INF);

    for (int q = 0; q < Q; ++q) {
        int k;
        std::cin >> k;
        if (k == 0) {
            int l, r, x;
            std::cin >> l >> r >> x;
            seg.update(l, r + 1, x);
        } else {
            int l, r;
            std::cin >> l >> r;
            std::cout << seg.query(l, r + 1) << std::endl;
        }
    }
    return 0;
}