#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define pb push_back #define eb emplace_back using namespace std; typedef long long ll; namespace FastIO{ char buf[1<<20],*p=buf+(1<<20); char getc(){ if(p==buf+(1<<20))fread(buf,1<<20,1,stdin),p=buf; return *(p++); } template<typename T> void read(T&x){ x=0;char ch=getc(); while(ch<'0'||ch>'9')ch=getc(); while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getc(); } char out[1<<20],*q=out; void putc(char c){ *(q++)=c; if(q==out+(1<<20))fwrite(out,1<<20,1,stdout),q=out; } int s[55]; template<typename T> void write(T x){ int top=0; do s[top++]=x%10,x/=10;while(x); for(;top;putc(s[--top]+'0')); } void flush(){fwrite(out,q-out,1,stdout);} } using FastIO::read; using FastIO::putc; using FastIO::write; const int maxn=4e5+10; int n,m; struct nd{ int a,b,c,d,v; }d[maxn]; struct que{ int x,l,r,sgn,id; }t[maxn]; ll res[maxn]; int a[maxn],fa[maxn]; int fa2[maxn]; int B[maxn]; ll S[maxn]; inline int fd(int u){if(fa[u]==u)return u;return fa[u]=fd(fa[u]);} inline int fd2(int u){if(fa2[u]==u)return u;return fa2[u]=fd2(fa2[u]);} int aa[maxn]; struct info{ int l,r,v; }qwq[maxn]; vector<int>ins[maxn],del[maxn]; ll sum[maxn]; vector<int>ask[maxn]; int s2[maxn]; ll s3[maxn]; pi ap[maxn]; void slv(){ read(n),read(m); up(i,1,n)read(d[i].a),read(d[i].b),read(d[i].c),read(d[i].d),read(d[i].v); sort(d+1,d+n+1,[&](nd a,nd b){return a.v>b.v;}); int q=0; up(i,1,m){ int a,b,c,d;read(a),read(b),read(c),read(d); t[++q]=(que){b,c,d,1,i}; if(a>1)t[++q]=(que){a-1,c,d,-1,i}; } int b=sqrt(n); for(int l=1;l<=n;l+=b){ int r=min(l+b-1,n); up(j,1,n+1)a[j]=0,fa[j]=j; vector<int>v={0,n}; up(j,1,n){ int L=max(d[j].a,l),R=min(d[j].b,r); if(L<=R){ if(L==l&&R==r); else v.eb(d[j].c-1),v.eb(d[j].d); } } up(j,1,q){ if(l<=t[j].x&&t[j].x<=r) v.eb(t[j].l-1),v.eb(t[j].r); } sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); up(i,l,r)ins[i].clear(),del[i].clear(); up(i,0,(int)v.size()-2)S[i]=0; up(j,1,n)s2[j]=s3[j]=0; up(j,1,n){ int L=max(d[j].a,l),R=min(d[j].b,r); if(L<=R){ if(L==l&&R==r){ int x=d[j].c,y=d[j].d; for(x=fd(x);x<=y;fa[x]=fd(x+1),x=fa[x]) a[x]=d[j].v; }else{ int xl=lower_bound(v.begin(),v.end(),d[j].c-1)-v.begin(); int xr=lower_bound(v.begin(),v.end(),d[j].d)-v.begin(); ins[L].eb(j),del[R+1].eb(j); qwq[j]=(info){xl,xr-1,d[j].v}; } } } up(i,1,n)aa[i]=a[i]; up(i,0,(int)v.size()-2){ int l=v[i]+1,r=v[i+1]; up(j,l,r)ap[j]={a[j],j}; sort(ap+l,ap+r+1); up(j,l,r)a[j]=ap[j].p1,aa[j]=ap[j].p2; sum[l]=a[l];up(j,l+1,r)sum[j]=sum[j-1]+a[j]; } up(j,1,q)if(l<=t[j].x&&t[j].x<=r)ask[t[j].x].eb(j); set<int>st; int top=0; up(j,l,r){ up(k,0,(int)v.size())fa2[k]=k,B[k]=0; for(int x:ins[j])st.insert(x); for(int x:del[j])st.erase(x); for(int p:st){ auto[l,r,v]=qwq[p]; for(int x=fd2(l);x<=r;fa2[x]=fd2(x+1),x=fa2[x]) B[x]=v; } ll D=0; up(k,0,(int)v.size()-2){ int pl=v[k]+1,pr=v[k+1]; ll val=0; if(a[pr]<=B[k])val=B[k]*1ll*(pr-pl+1),s2[pr]++,s3[pr]+=B[k]; else if(a[pl]>=B[k])val=sum[pr]; else{ int u=lower_bound(a+pl,a+pr,B[k])-a;s2[u-1]++,s3[u-1]+=B[k]; val=(u-pl)*1ll*B[k]+sum[pr]-sum[u-1]; } D+=val,S[k]+=D; } for(int p:ask[j]){ int L=lower_bound(v.begin(),v.end(),t[p].l-1)-v.begin(); int R=lower_bound(v.begin(),v.end(),t[p].r)-v.begin(); res[t[p].id]+=t[p].sgn*(S[R-1]-(L?S[L-1]:0)); } } int len=r-l+1; up(i,1,n)sum[i]=0; up(i,0,(int)v.size()-2){ int l=v[i]+1,r=v[i+1]; int c1=0;ll c2=0; down(k,r,l){ c1+=s2[k],c2+=s3[k]; ll nex=a[k]*1ll*(len-c1)+c2; sum[aa[k]]=nex; } } up(i,1,n)sum[i]+=sum[i-1]; up(j,1,q){ if(t[j].x>r) res[t[j].id]+=t[j].sgn*(sum[t[j].r]-sum[t[j].l-1]); } } up(i,1,m)write(res[i]),putc(10); } int main(){ // freopen("hoshino.in","r",stdin),freopen("hoshino.out","w",stdout); slv();FastIO::flush(); return 0; }