#include #include #include #include #include using namespace std; using namespace atcoder; const long long mod=1000000000000000009; using S =vector; using F =vector; S op(S l, S r) { S retu(6); for(int i=0;i<6;i++){ retu[i]=(l[i]+r[i])%mod; } return retu; } S e() { return S(6,0ll); } F composition(F l, F r) { for(int i=0;i<5;i++){ if(l[i]){ F retu(5,0ll); retu[i]=(l[i]+r[i])%mod; return retu; } } F retu(5); for(int i=0;i<5;i++){ retu[i]=r[i]; } return retu; } S mapping(F l, S r) { for(int i=0;i<5;i++){ if(l[i]){ S retu(6,0ll); retu[i]=(r[i]+l[i]*r[5]%mod)%mod; retu[5]=r[5]; return retu; } } S retu(6,0ll); for(int i=0;i<6;i++){ retu[i]=r[i]; } return retu; } F id() { return F(5,0ll); } int main() { int N; cin >> N; vector ans(5,0ll); int Q; cin >> Q; vector X(Q),bound; vector L(Q),R(Q); bound={0ll,1000000000000000ll}; for(int q=0;q>X[q]>>L[q]>>R[q]; R[q]+=1; bound.push_back(L[q]); bound.push_back(R[q]); } sort(bound.begin(), bound.end()); bound.erase(unique(bound.begin(), bound.end()), bound.end()); unordered_map comp; int le=bound.size()-1; for (int i = 0; i < le+1; ++i) { comp[bound[i]] = i; } for(int q=0;q a(le); for(int i=0;i seg(a); for(int q=0;q=2){ continue; } for(int i=0;i<5;i++){ if(vec[i]==m){ ans[i]+=m; ans[i]%=mod; } } } } S vec=seg.all_prod(); for(int i=0;i<5;i++){ ans[i]+=vec[i]; ans[i]%=mod; } for(int i=0;i<5;i++){ if(i){ cout<<" "; } cout<