#include using namespace std; using ll = long long; struct Ops1 { struct T { ll val; int size; }; using F = ll; static constexpr T identity = {0, 1}; static constexpr F lazy_identity = 0; static T op(T a, T b) {return {a.val + b.val, a.size + b.size};} static T mapping(F f, T x) {return {x.val + f * x.size, x.size};} static F composition(F f, F g) {return f + g;} static bool ok(T a) {return true;} }; template struct LazySegTree { using T = typename Ops::T; using F = typename Ops::F; int N, size, log; vector tree1; vector lazy; LazySegTree(int N) : LazySegTree(vector(N, Ops::identity)) {} LazySegTree(const vector& arr) : N(arr.size()), size(1), log(0) { while(size < N) size <<= 1, log++; tree1.assign(2 * size, Ops::identity); lazy.assign(size, Ops::lazy_identity); for(int i=0; i0; i--) update(i); } void set(int p, T x) { p += size; for(int i=log; i>=1; i--) push(p >> i); tree1[p] = x; for(int i=1; i<=log; i++) update(p >> i); } T operator[](int p) { p += size; for(int i=log; i>=1; i--) push(p >> i); return tree1[p]; } T query(int l, int r) { if(l == r) return Ops::identity; T ret = Ops::identity; l += size, r += size; for(int i=log; i>=1; i--) { if(((l >> i) << i) != l) push(l >> i); if(((r >> i) << i) != r) push((r - 1) >> i); } while(l < r) { if(l & 1) ret = Ops::op(ret, tree1[l++]); if(r & 1) ret = Ops::op(ret, tree1[--r]); l >>= 1, r >>= 1; } return ret; } T all_query() { return tree1[1]; } void apply(int p, F f) { p += size; for(int i=log; i>=1; i--) push(p >> i); tree1[p] = Ops::mapping(f, tree1[p]); for(int i=1; i<=log; i++) update(p >> i); } void apply(int l, int r, F f) { if(l == r) return; l += size, r += size; for(int i=log; i>=1; i--) { if(((l >> i) << i) != l) push(l >> i); if(((r >> i) << i) != r) push((r - 1) >> i); } int tl = l, tr = r; while(l < r) { if(l & 1) all_apply(l++, f); if(r & 1) all_apply(--r, f); l >>= 1, r >>= 1; } l = tl, r = tr; for(int i=1; i<=log; i++) { if(((l >> i) << i) != l) update(l >> i); if(((r >> i) << i) != r) update((r - 1) >> i); } } int max_right(int l) { if(l == N) return N; l += size; for(int i=log; i>=1; i--) push(l >> i); T acc = Ops::identity; do { while((l & 1) == 0) l >>= 1; if(!Ops::ok(Ops::op(acc, tree1[l]))) { while(l < size) { push(l); l <<= 1; if(Ops::ok(Ops::op(acc, tree1[l]))) { acc = Ops::op(acc, tree1[l]); l++; } } return l - size; } acc = Ops::op(acc, tree1[l]); l++; } while((l & -l) != l); return N; } int min_left(int r) { if(r == 0) return 0; r += size; for(int i=log; i>=1; i--) push((r - 1) >> i); T acc = Ops::identity; do { r--; while(r > 1 && (r & 1)) r >>= 1; if(!Ops::ok(Ops::op(acc, tree1[r]))) { while(r < size) { push(r); r = (r << 1) + 1; if(Ops::ok(Ops::op(acc, tree1[r]))) { acc = Ops::op(acc, tree1[r]); r--; } } return r + 1 - size; } acc = Ops::op(acc, tree1[r]); } while((r & -r) != r); return 0; } void update(int p) {tree1[p] = Ops::op(tree1[p*2], tree1[p*2+1]);} void all_apply(int k, F f) { tree1[k] = Ops::mapping(f, tree1[k]); if(k < size) lazy[k] = Ops::composition(f, lazy[k]); } void push(int k) { all_apply(2 * k, lazy[k]); all_apply(2 * k + 1, lazy[k]); lazy[k] = Ops::lazy_identity; } void debug() { for(int i=1; i<=2*size; i++) cout << tree1[i-1].val << " \n"[(i & -i) == i]; for(int i=2; i<=size; i++) cout << lazy[i-1] << " \n"[(i & -i) == i]; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll N, M, ans = 0; cin >> N >> M; LazySegTree tree1(M), tree2(M); vector A(N), L(N), R(N), H(N); for(int i=0; i> A[i] >> L[i] >> R[i]; tree1.apply(L[i] - 1, R[i], 1LL); ans += (R[i] - (L[i] - 1)) * A[i]; H[i] = i; tree2.set(i, Ops1::T{A[i], 1}); } for(int i=0; i> Q; while(Q--) { int X, Y, U, V; cin >> X >> Y >> U >> V; X--, Y--; ans += tree1[H[X]].val * A[X]; ans -= (R[X] - (L[X] - 1)) * A[X]; tree2.set(H[X], Ops1::T{0, 0}); ans += tree2.query(L[X] - 1, R[X]).val; tree1.apply(L[X] - 1, R[X], -1); tree1.apply(U - 1, V, 1); ans -= tree1[Y].val * A[X]; ans += (V - (U - 1)) * A[X]; ans -= tree2.query(U - 1, V).val; tree2.set(Y, Ops1::T{A[X], 1}); cout << ans << endl; H[X] = Y; L[X] = U; R[X] = V; } }