struct node {
    ll val;

    node(){
        val = 0;
    }

    node(ll x){
        val = x;
    }

    void change(ll x){
        val += x;
    }
};

struct Lazy{
    vector < node > tree , lazy;
    int tree_size;

    Lazy(int n){
        tree_size = 1;
        while (tree_size < n) tree_size *= 2;
        tree.assign(2 * tree_size , node(1e18));
        lazy.assign(2 * tree_size , node());
    }

    node merge(node a , node b){
        node res = node();
        res.val = min(a.val , b.val);
        return res;
    }

    void build(vector < ll > &v , int x , int lx , int rx){
        if(rx - lx == 1){
            if(lx < sz(v)) tree[x] = node(v[lx]);
            return;
        }

        int m = (lx + rx) / 2;
        build(v , 2 * x + 1 , lx , m);
        build(v , 2 * x + 2 , m , rx);
        tree[x] = merge(tree[2 * x + 1] , tree[2 * x + 2]);
    }

    void build(vector < ll > &v){
        build(v , 0 , 0 , tree_size);
    }

    void push(int x , int lx , int rx){
        if(lazy[x].val){
            tree[x].val += lazy[x].val;
            if(rx - lx != 1){
                lazy[2 * x + 1].val += lazy[x].val;
                lazy[2 * x + 2].val += lazy[x].val;
            }
            lazy[x].val = 0;
        }
    }

    void update(int l , int r , int val , int x , int lx , int rx){
        push(x , lx , rx);
        if(lx >= r || rx <= l) return;
        if(lx >= l && rx <= r){
            tree[x].val += val;
            if(rx - lx != 1){
                lazy[x * 2 + 1].val += val;
                lazy[x * 2 + 2].val += val;
            }
            return;
        }

        int m = (lx + rx) / 2;
        update(l , r , val , 2 * x + 1 , lx , m);
        update(l , r , val , 2 * x + 2 , m , rx);
        tree[x] = merge(tree[2 * x + 1] , tree[2 * x + 2]);
    }

    void update(int l , int r , int val){
        update(l , r , val , 0 , 0 , tree_size);
    }

    node query(int l , int r , int x , int lx , int rx){
        push(x , lx , rx);
        if(lx >= r || rx <= l) return node(1e18);
        if(lx >= l && rx <= r) return tree[x];

        int m = (lx + rx) / 2;
        node left = query(l , r , 2 * x + 1 , lx , m);
        node right = query(l , r , 2 * x + 2 , m , rx);
        return merge(left , right);
    }

    node query(int l , int r) {
        return query(l, r, 0, 0, tree_size);
    }

};