struct seg_tree1 {
    int n;
    vector<int> sum, add;

    seg_tree1(int _n) {
        n = _n;
        sum.resize(4*n);
        add.resize(4*n);
    }

    void upd(int l, int r, int lx, int rx, int v, int x) {
        if (l >= rx || r <= lx) return;
        sum[v] += (min(r, rx)-max(l, lx)) * x;

        if (l >= lx && r <= rx) {
            add[v] += x;
            return;
        }
        int m = (l + r) / 2;
        upd(l, m, lx, rx, v*2+1, x);
        upd(m, r, lx, rx, v*2+2, x);
    }
    void upd(int l, int r, int x) {
        upd(0, n, l, r+1, 0, x);
    }

    int ask(int l, int r, int lx, int rx, int v) {
        if (l >= rx || r <= lx) return 0;
        if (l >= lx && r <= rx) {
            return sum[v];
        }
        int m = (l + r) / 2;
        return ask(l, m, lx, rx, v*2+1) + ask(m, r, lx, rx, v*2+2) + (min(r, rx)-max(l, lx)) * add[v];
    }
    int ask(int l, int r) {
        return ask(0, n, l, r+1, 0);
    }
};

struct seg_tree2 {
    int n, m;
    vector<seg_tree1> sum, add;
    seg_tree2(int _n, int _m) {
        n = _n; m = _m;
        sum.resize(4*n, seg_tree1(m));
        add.resize(4*n, seg_tree1(m));
    }

    void upd(int l1, int r1, int lx, int rx, int l2, int r2, int v, int x) {
        if (l1 >= rx || r1 <= lx) return;

        sum[v].upd(l2, r2, x * (min(rx, r1) - max(lx, l1)));
        if (l1 >= lx && r1 <= rx) {
            add[v].upd(l2, r2, x);
            return;
        }
        int med = (l1 + r1) / 2;
        upd(l1, med, lx, rx, l2, r2, v*2+1, x);
        upd(med, r1, lx, rx, l2, r2, v*2+2, x);
    }

    int ask(int l1, int r1, int lx, int rx, int l2, int r2, int v) {
        if (l1 >= rx || r1 <= lx) return 0;
        if (l1 >= lx && r1 <= rx) {
            return sum[v].ask(l2, r2);
        }
        int med = (l1 + r1) / 2;
        return ask(l1, med, lx, rx, l2, r2, v*2+1) + ask(med, r1, lx, rx, l2, r2, v*2+2)
               + add[v].ask(l2, r2) * (min(rx, r1) - max(lx, l1));
    }
};