#include <bits/stdc++.h>

struct S { ... }; // Segment tree element type
const S e = ...; // The identity element
S op(S a, S b) { ... } // Compute a · b

struct F { ... }; // Lazy mapping type
const F id = ...; // The identity mapping
S mapping(F f, S x) { ... } // Compute f(x)
F composition(F f, F g) { ... } // Compute f ∘ g
F inv(F f) { ... } // Compute f^(-1)

class lazy_segtree {
    public:
    explicit lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
        size = 1; log = 0;
        while (size < _n) size *= 2, log++;
        d = std::vector<S>(2 * size, e);
        lz = std::vector<F>(size, id);
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) d[i] = op(d[2 * i], d[2 * i + 1]);
    }

    S prod(int l, int r) const { // const!!!
        return prod(1, 0, size, id, l, r);
    }

    void apply(int l, int r, F f) {
        apply(1, 0, size, id, l, r, f);
    }

    public:
    int _n, size, log;
    std::vector<S> d;
    std::vector<F> lz;

    void update(int k) { d[k] = mapping(lz[k], op(d[2 * k], d[2 * k + 1])); }
    void all_apply(int k, F f) {
        d[k] = mapping(f, d[k]);
        if (k < size) lz[k] = composition(f, lz[k]);
    }

    S prod(int k, int cl, int cr, F g, int l, int r) const { // const!!!
        if (l <= cl && cr <= r) return mapping(g, d[k]);

        int cm = (cl + cr) / 2;
        F h = composition(g, lz[k]);
        if (r <= cm) return prod(2 * k, cl, cm, h, l, r);
        if (l >= cm) return prod(2 * k + 1, cm, cr, h, l, r);
        return op(prod(2 * k, cl, cm, h, l, r),
                  prod(2 * k + 1, cm, cr, h, l, r));
    }

    void apply(int k, int cl, int cr, F g, int l, int r, F f) {
        if (l <= cl && cr <= r) {
            all_apply(k, composition(inv(g), composition(f, g)));
            return;
        }

        int cm = (cl + cr) / 2;
        F h = composition(g, lz[k]);
        if (r <= cm) 
            apply(2 * k, cl, cm, h, l, r, f);
        else if (l >= cm)
            apply(2 * k + 1, cm, cr, h, l, r, f);
        else {
            apply(2 * k, cl, cm, h, l, r, f);
            apply(2 * k + 1, cm, cr, h, l, r, f);
        }
        update(k);
    }
};