struct SegmentTree {
    vector<ll> t;
    vector<ll> a;
    SegmentTree(int n) : t(n * 4), a(n * 4) {}
    void Push(int v, int tl, int tr) {
        t[v] += a[v];
        if (tl + 1 < tr) {
            a[v * 2 + 1] += a[v];
            a[v * 2 + 2] += a[v];
        }
        a[v] = 0;
    }
    void Update(int v, int tl, int tr, int l, int r, ll value) {
        Push(v, tl, tr);
        if (tl >= r || tr <= l) return;
        if (tl >= l && tr <= r) {
            a[v] += value;
            Push(v, tl, tr);
        } else {
            int tm = (tl + tr) >> 1;
            Update(v * 2 + 1, tl, tm, l, r, value);
            Update(v * 2 + 2, tm, tr, l, r, value);
            t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
        }
    }
    ll Get(int v, int tl, int tr, int l, int r) {
        Push(v, tl, tr);
        if (tl >= r || tr <= l) return -1e18;
        if (tl >= l && tr <= r) return t[v];
        int tm = (tl + tr) >> 1;
        return max(Get(v * 2 + 1, tl, tm, l, r), Get(v * 2 + 2, tm, tr, l, r));
    }
};