//二次更新 2024.2.22
template<class Info, class Tag>
struct LazySegmentTree {
    int n;
    vector<Info> info;
    vector<Tag> tag;
    LazySegmentTree(): n(0) {}
    LazySegmentTree(int n_, Info v_ = Info()) {
        init(n_, v_);
    }
    template<class T> 
    LazySegmentTree(vector<T> init_) {
        init(init_);
    }
    void init(int n_, Info v_ = Info()) {
        init(vector<Info>(n_, v_));
    }
    template<class T>
    void init(vector<T> init_) {
        n = init_.size() - 1;//init_ 下标从1开始!!!!
        info.assign((n + 11) << 2, Info());
        tag.assign((n + 11) << 2, Tag());
        function<void(int, int, int)> build = [&](int id, int l, int r) {
            if (l == r) {
                info[id] = init_[l];
                return;
            }
            int mid = (l + r) / 2;
            build(id * 2, l, mid);
            build(id * 2 + 1, mid + 1, r);
            pull(id);
        };
        build(1, 1, n);
    }
    //向上合并更新
    void pull(int id) {
        info[id] = info[id * 2] + info[id * 2 + 1];
    }
    //加Tag
    void apply(int id, const Tag &v) {
        info[id].apply(v);
        tag[id].apply(v);
    }
    //下传Tag
    void push(int id) {
        apply(id * 2, tag[id]);
        apply(id * 2 + 1, tag[id]);
        tag[id] = Tag();
    }
    //单点修改
    void change(int id, int l, int r, int x, const Info &v) {
        if (l == x and r == x) {
            info[id] = v;
            return;
        }
        push(id);
        int mid = (l + r) / 2;
        if (x <= mid) change(id * 2, l, mid, x, v);
        else change(id * 2 + 1, mid + 1, r, x, v);
        pull(id);
    }
    void change(int x, const Info &v) {
        change(1, 1, n, x, v);
    }
    //区间修改
    void modify(int id, int l, int r, int ql, int qr, const Tag &v) {
        if (l == ql and r == qr) {
            apply(id, v);
            return;
        }
        push(id);
        int mid = (l + r) / 2;
        if (qr <= mid) modify(id * 2, l, mid, ql, qr, v);
        else if (ql > mid) modify(id * 2 + 1, mid + 1, r, ql, qr, v);
        else {
            modify(id * 2, l, mid, ql, mid, v); 
            modify(id * 2 + 1, mid + 1, r, mid + 1, qr, v);
        }
        pull(id);
    }
    void modify(int l, int r, const Tag &v) {
        modify(1, 1, n, l, r, v);
    }
    //区间查询
    Info rangeQuery(int id, int l, int r, int ql, int qr) {
        if (l == ql and r == qr) {
            return info[id];
        }
        push(id);
        int mid = (l + r) / 2;
        if (qr <= mid) return rangeQuery(id * 2, l, mid, ql, qr);
        else if (ql > mid) return rangeQuery(id * 2 + 1, mid + 1, r, ql, qr);
        else return rangeQuery(id * 2, l, mid, ql, mid) + 
                    rangeQuery(id * 2 + 1, mid + 1, r, mid + 1, qr);
    }
    Info rangeQuery(int l, int r) {
        return rangeQuery(1, 1, n, l, r);
    }
    //后面更新 findFirst 和 findLast 功能
};
struct Tag {
    //Tag date:
    Tag(): () {}
    Tag(): () {}
    void apply(Tag t) {
        //to do
    }
};
struct Info {
    //Info date:
    Info(): () {}
    Info(): () {}
    void apply(Tag t) {
        //to do
    }
};
Info operator+(const Info &a, const Info &b) {
    Info c;
    //to do
    return c;
}