struct Node {
int v, lz, ls, rs;
Node(): v(0), lz(0), ls(0), rs(0) {}
};
class SegTree {
vector<Node> tr;
int cnt;
void push_down(int p, int len) {
if (!tr[p].ls) tr[p].ls = ++cnt, tr.emplace_back(Node{});
if (!tr[p].rs) tr[p].rs = ++cnt, tr.emplace_back(Node{});
if (!tr[p].lz) return;
int lz = tr[p].lz;
tr[tr[p].ls].v = len / 2 * lz;
tr[tr[p].rs].v = (len - len / 2) * lz;
tr[tr[p].ls].lz = tr[tr[p].rs].lz = lz;
tr[p].lz = 0;
}
void push_up(int p) {
tr[p].v = tr[tr[p].ls].v + tr[tr[p].rs].v;
}
public:
SegTree(): tr(1), cnt(0) {
tr.reserve(500000);
}
void modify(int l, int r, int L, int R, int v, int p = 0) {
if (l <= L && r >= R) {
tr[p].lz = v, tr[p].v = v * (R - L + 1);
return;
}
int mid = (L + R - 1) / 2;
push_down(p, R - L + 1);
if (mid >= l) modify(l, r, L, mid, v, tr[p].ls);
if (mid < r) modify(l, r, mid + 1, R, v, tr[p].rs);
push_up(p);
}
int query(int l, int r, int L, int R, int p = 0) {
if (l <= L && r >= R) return tr[p].v;
int mid = (L + R - 1) / 2, ret = 0;
push_down(p, R - L + 1);
if (mid >= l) ret += query(l, r, L, mid, tr[p].ls);
if (mid < r) ret += query(l, r, mid + 1, R, tr[p].rs);
return ret;
}
};