template <class T>
struct SegmentTree {
    struct vertex{
        int l, r;
        T d;
        int id;

        inline int Lchild() { return id * 2; }
        inline int Rchild() { return id * 2 + 1;};
    };

    vector<vertex> t;

    void build(int id, int l, int r){
        t[id] = {l, r, T(), id};
        if (l == r){
            return;
        }
        int m = (l + r) / 2;
        build(t[id].Lchild(), l, m);
        build(t[id].Rchild(), m + 1, r);
    }

    SegmentTree(int n_){
        t.resize(n_ * 4);
        build(1, 0, n_ - 1);
    }

    template <class BinaryOperation>
    void update(int id, BinaryOperation op){
        if (t[id].l == t[id].r)
            return;
        t[id].d = op(t[t[id].Lchild()].d, t[t[id].Rchild()].d);
    }

    template <class BinaryOperation>
    void push(int id, BinaryOperation op){
        if (t[id].l == t[id].r)
            return;
        t[t[id].Lchild()].d.push(t[id].d);
        t[t[id].Rchild()].d.push(t[id].d);
        t[id].d.pushclear();
        update(id, op);
    }

    template <class UnaryOperation, class BinaryOperation>
    void process(int id, int l, int r, UnaryOperation op, BinaryOperation upd) {
        if (t[id].l > r || t[id].r < l) {
            return;
        }
        push(id, upd);
        if (l <= t[id].l && t[id].r <= r) {
            op(t[id].d);
            push(id, upd);
            return;
        }
        process(t[id].Lchild(), l, r, op, upd);
        process(t[id].Rchild(), l, r, op, upd);
        update(id, upd);
    }
};