struct SegmentTree {
    vector<ll> tree, lazy, l, r;

    SegmentTree(int size) : tree(4 * size), lazy(4 * size), l(4 * size), r(4 * size) {
        init(1, 0, size - 1);
    }

    // Functions to update when query changes =============================

    ll best(ll lCalc, ll rCalc) {
        return lCalc + rCalc;
    }

    void upd(int i) {
        tree[i] = best(tree[i << 1] + lazy[i << 1], tree[i << 1 | 1] + lazy[i << 1 | 1]);
    }


    void prob(int i) {
        lazy[i << 1] += lazy[i];
        lazy[i << 1 | 1] += lazy[i];
        lazy[i] = 0;
    }

    // ====================================================================

    void inc(int s, int e, ll v, int i = 1) {
        if(s > r[i] || e < l[i])
            return;

        if(s <= l[i] && e >= r[i]) {
            lazy[i] += v;
            return;
        }

        prob(i);

        inc(s, e, v, i << 1);
        inc(s, e, v, i << 1 | 1);

        upd(i);
    }


    ll qry(int s, int e, int i = 1) {
        if(s > r[i] || e < l[i]) // change the return value depending on the query
            return 0;

        if(s <= l[i] && e >= r[i]) // may change if the query change
            return tree[i] + lazy[i];

        prob(i);

        ll lCalc = qry(s, e, i << 1);
        ll rCalc = qry(s, e, i << 1 | 1);

        upd(i);

        return best(lCalc, rCalc);
    }

    void init(int i, int s, int e) {
        l[i] = s;
        r[i] = e;

        if(s == e)
            return;

        int m = s + ((e - s) >> 1);

        init(i << 1, s, m);
        init(i << 1 | 1, m + 1, e);
    }
};