#include using namespace std; struct Init { Init() { ios::sync_with_stdio(0); cin.tie(0); cout << setprecision(13); } }init; using ll = long long; using ull = unsigned long long; using pii = pair; using pll = pair; template using minpq=priority_queue,greater>; #define rep(i, x, limit) for(int i=(x); i< (limit); ++i) #define REP(i, x, limit) for(int i=(x); i<=(limit); ++i) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define el '\n' #define spa ' ' #define Yes cout<<"Yes"< std::ostream &operator<< (std::ostream &os, std::pair p){ os << "{" << p.first << "," << p.second << "}"; return os; } template inline bool chmin(T1 &a,T2 b){return a>b?a=b,true:false;} template inline bool chmax(T1 &a,T2 b){return a=0); if(a==0 and b==0) return 1; if(a==1) return 1; if(a==-1) return (b&1)?-1:1; ll res=1; while(b){ if(b&1) res*=a; b>>=1; if(b) a*=a; } return res; } // 配列の要素を空白区切りで出力 第二引数をtrueにすると改行区切り template inline void print_vec(const vector &v, bool split_line=false) { if(v.empty()){ cout << "This vector is empty." << el; return; } constexpr bool isValue = is_integral::value; for (int i = 0; i < (int)v.size(); i++) { if constexpr(isValue){ if((v[i]==inf) || (v[i]==infl)) cout << 'x' << " \n"[split_line || i+1==(int)v.size()]; else cout << v[i] << " \n"[split_line || i+1==(int)v.size()]; }else cout << v[i] << " \n"[split_line || i+1==(int)v.size()]; } } // This function sorts multiple vectors based on the first vector // and returns the indices of the sorted order. // Note: First argument is a comparison function. template vector multipleSort(Compare comp = Compare(), Vectors&... vectors) { const size_t size = std::get<0>(std::tie(vectors...)).size(); ((void)std::initializer_list{(vectors.size() == size ? 0 : throw std::invalid_argument("Vectors must have the same size"))...}); std::vector indices(size); std::iota(indices.begin(), indices.end(), 0); std::sort(indices.begin(), indices.end(), [&](size_t i, size_t j) { return comp(std::get<0>(std::tie(vectors...))[i], std::get<0>(std::tie(vectors...))[j]); }); auto reorder = [&](auto& vec) { auto temp=vec; for (size_t i = 0; i < size; ++i) { vec[i] = temp[indices[i]]; } }; (reorder(vectors), ...); return indices; } #include #include using S=ll; using F=ll; S op(S a,S b){ return max(a,b); } S e(){ return 0; } S mapping(F f,S x){ return f+x; } F composition(F f,F g){ return f+g; } F id(){ return 0; } int main(){ int N,M; cin>>N>>M; vector A(N),L(N),R(N); atcoder::fenwick_tree fw(M); atcoder::lazy_segtree seg(M); rep(i,0,N){ cin>>A[i]>>L[i]>>R[i],L[i]--; fw.add(i,A[i]); seg.apply(L[i],R[i],1); } vector pos(N); rep(i,0,N) pos[i]=i; ll ans=0; rep(i,0,N){ ans+=A[i]*(R[i]-L[i])-fw.sum(L[i],R[i]); } int Q; cin>>Q; while(Q--){ ll x,y,u,v; cin>>x>>y>>u>>v; x--,y--; seg.apply(L[x],R[x],-1); ans+=seg.get(pos[x])*A[x]; ans-=A[x]*(R[x]-L[x])-fw.sum(L[x],R[x]); fw.add(pos[x],-A[x]); pos[x]=y; fw.add(pos[x],A[x]); ans-=seg.get(pos[x])*A[x]; L[x]=u-1,R[x]=v; seg.apply(L[x],R[x],1); ans+=A[x]*(R[x]-L[x])-fw.sum(L[x],R[x]); cout<