template <class V, int SZ> struct lazy {
    // Remember to change everything!
    const V ne = 0, MADD = 0, VAL = 0, MSET = 1e18;
    vector<V> val, madd, mset;
    lazy() {
        val = madd = mset = vector<V>(2 * SZ);
        vector<V> sp;
        build(0, SZ, 1, sp);
    }
    lazy(vector<V> x) {
        val = madd = mset = vector<V>(2 * SZ);
        build(0, SZ, 1, x);
    }
    void pull(int ind) {
        val[ind] = val[ind * 2] + val[ind * 2 + 1];
    }
    void build(int lo, int hi, int ind, vector<V> &v) {
        if (lo + 1 < hi) {
            int mid = (lo + hi) / 2;
            build(lo, mid, ind * 2, v);
            build(mid, hi, ind * 2 + 1, v);
            pull(ind);
        } else
            val[ind] = (lo < (int)v.size() ? v[lo] : VAL);
        mset[ind] = MSET, madd[ind] = MADD;
    }
    V query(int L, int R, int ind = 1, int lo = 0, int hi = SZ) {
        if (R <= lo || hi <= L) return ne;
        if (L <= lo && hi <= R) return val[ind];
        push(ind, lo, hi);
        int mid = (lo + hi) / 2;
        return query(L, R, ind * 2, lo, mid) +
               query(L, R, ind * 2 + 1, mid, hi);
    }
    void set(int L, int R, V x, int ind = 1, int lo = 0, int hi = SZ) {
        if (R <= lo || hi <= L) return;
        if (L <= lo && hi <= R)
            mset[ind] = x, val[ind] = mset[ind] * (hi - lo), madd[ind] = 0;
        else {
            push(ind, lo, hi);
            int mid = (lo + hi) / 2;
            set(L, R, x, ind * 2, lo, mid);
            set(L, R, x, ind * 2 + 1, mid, hi);
            pull(ind);
        }
    }
    void add(int L, int R, V x, int ind = 1, int lo = 0, int hi = SZ) {
        if (R <= lo || hi <= L) return;
        if (L <= lo && hi <= R) {
            if (mset[ind] != MSET)
                mset[ind] += x;
            else
                madd[ind] += x;
            val[ind] += x * (hi - lo);
        } else {
            push(ind, lo, hi);
            int mid = (lo + hi) / 2;
            add(L, R, x, ind * 2, lo, mid);
            add(L, R, x, ind * 2 + 1, mid, hi);
            pull(ind);
        }
    }
    void push(int ind, int lo, int hi) {
        int mid = (lo + hi) / 2;
        if (mset[ind] != MSET) {
            set(lo, mid, mset[ind], ind * 2, lo, mid);
            set(mid, hi, mset[ind], ind * 2 + 1, mid, hi);
            mset[ind] = MSET;
        } else if (madd[ind] != MADD) {
            add(lo, mid, madd[ind], ind * 2, lo, mid);
            add(mid, hi, madd[ind], ind * 2 + 1, mid, hi);
            madd[ind] = 0;
        }
    }
};