传送门

不太优美的暴力题,直接在线段树的每个节点上维护所有乘上去的一次多项式,然后最后每个节点暴力分治乘起来之后,在区间的每个点上多点求值就行了。

太懒了所以就用了他给的板子(惭愧

不过这个板子竟然不支持负数,我就因为这个WA了半天。。。

#include<bits/stdc++.h>
using namespace std;

namespace Poly{
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define re(i,a,b) for(int i=(a);i<(b);i++)
#define repd(i,a,b) for(int i=(a);i>=(b);i--)
#define il inline
#define all(a) a.begin(),a.end()
#define adm(a,b,c) {a=a+b;if(a>=c)a-=c;else if(a<0)a+=c;}
#define ll long long
#define ls (k<<1)
#define rs (k<<1|1)
    const int N=5e6+5,M=1e7+5,INF=1e9,mod=998244353;
    il ll qpow(ll a,ll b,ll p){ll ret=1;for(;b;b>>=1,a=a*a%p)if(b&1)ret=ret*a%p;return ret;}
    int rev[N],oo;
    il int inv(int x){return qpow(x,mod-2,mod);}
    void fft(int*a,int n,int opt){oo+=n;
        int l=0;for(int o=1;o<n;o<<=1)l++;
        re(i,0,n)rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
        re(i,0,n)if(i<rev[i])swap(a[i],a[rev[i]]);
        for(int i=1;i<n;i<<=1){
            int wn=qpow(3,(mod-1)/(i*2),mod);if(opt==-1)wn=inv(wn);
            for(int j=0;j<n;j+=i+i){
                int w=1;re(k,0,i){
                    int x=a[j+k],y=1ll*a[j+k+i]*w%mod;
                    a[j+k]=(x+y>=mod)?(x+y-mod):(x+y);
                    a[j+k+i]=(x-y<0)?(x-y+mod):(x-y);
                    w=1ll*w*wn%mod;
                }
            }
        }if(opt==-1){
            int iv=inv(n);
            re(i,0,n)a[i]=1ll*a[i]*iv%mod;
        }
    }
    struct poly{
        vector<int>a;
        il int siz(){return a.size()-1;}
        il void resiz(int x){a.resize(x+1);}
        il int&operator[](int x){return a[x];}
        il void mt(){
            int p=siz()+1;
            while(p&&!a[p-1])p--;
            resiz(p-1);
        }
        il void trans(int*b,int n){
            resiz(n);
            rep(i,0,n)a[i]=b[i];
            mt();
        }
    };
    int mula[N],mulb[N],mulc[N];
    il poly operator*(poly&a, poly&b){
        poly c;c.resiz(a.siz()+b.siz());
        if(a.siz()<50||b.siz()<50){
            rep(i,0,a.siz())rep(j,0,b.siz())c[i+j]=(c[i+j]+1ll*a[i]*b[j])%mod;
            return c;
        }
        int n=1;while(n<=a.siz()+b.siz())n<<=1;
        rep(i,0,n)mula[i]=mulb[i]=mulc[i]=0;
        rep(i,0,a.siz())mula[i]=a[i];
        rep(i,0,b.siz())mulb[i]=b[i];
        fft(mula,n,1);fft(mulb,n,1);
        rep(i,0,n)mulc[i]=1ll*mula[i]*mulb[i]%mod;
        fft(mulc,n,-1);
        c.trans(mulc,n);
        return c;
    }
    il poly operator+(poly&a,poly&b){
        poly c;c.resiz(max(a.siz(),b.siz()));
        rep(i,0,a.siz())c[i]=a[i];
        rep(i,0,b.siz())c[i]=(c[i]+b[i])%mod;
        c.mt();
        return c;
    }
    il poly operator-(poly a,poly b){
        poly c;c.resiz(max(a.siz(),b.siz()));
        rep(i,0,a.siz())c[i]=a[i];
        rep(i,0,b.siz())c[i]=(c[i]-b[i]+mod)%mod;
        c.mt();
        return c;
    }
    int inva[N],polya[N],invb[N];
    il void getinv(int n){
        if(n==1){inva[0]=inv(polya[0]);return;}
        getinv((n+1)>>1);
        int len=1;while(len<n+n+3)len<<=1;
        re(i,n,len)invb[i]=inva[i]=0;
        re(i,0,n)invb[i]=polya[i];
        fft(invb,len,1);fft(inva,len,1);
        re(i,0,len)inva[i]=1ll*inva[i]*((mod+2-(1ll*inva[i]*invb[i]%mod))%mod)%mod;
        fft(inva,len,-1);
        re(i,n,len)inva[i]=0;
    }
    il poly inv(poly&x){
        poly y;y.resiz(x.siz());
        rep(i,0,x.siz())polya[i]=x[i];
        getinv(x.siz()+1);
        y.trans(inva,x.siz());
        return y;
    }
    il void div(poly&a,poly&b,poly&d,poly&r){
        int n=a.siz(),m=b.siz();
        if(n<m){d.resiz(0);d[0]=0;r=a;return;}
        int len=1;while(len<n+n)len<<=1;
        poly ra=a,rb=b;reverse(all(ra.a));reverse(all(rb.a));
        rb.resiz(n-m);rb=inv(rb);
        d=ra*rb;d.resiz(n-m);reverse(all(d.a));
        r=a-(b*d);
        r.mt();
    }
    poly operator/(poly a,poly b){poly d,r;div(a,b,d,r);return d;}
    poly operator%(poly a,poly b){poly d,r;div(a,b,d,r);return r;}
    int qx[N],eres[N];
    il int bru_eval(poly a,int x){
        int res=0;
        repd(i,a.siz(),0)res=(1ll*res*x+a[i])%mod;
        return res;
    }
    poly mpoly[N];
    il void evaluation(int k,poly f,int m,int*x,int*res){
        if(f.siz()<=500||m<500){
            rep(i,0,m)res[i]=bru_eval(f,x[i]);
            return;
        }poly q0,q1,tmp;
        int mid=m>>1;
        q0=mpoly[ls];q1=mpoly[rs];
        evaluation(ls,f%q0,mid,x,res);
        evaluation(rs,f%q1,m-mid-1,x+mid+1,res+1+mid);
    }
    void eval_init(int k,int m,int*x){
        if(!m){
            mpoly[k].resiz(1);
            mpoly[k][1]=1;mpoly[k][0]=mod-x[0];
            return;
        }int mid=m>>1;
        eval_init(ls,mid,x);
        eval_init(rs,m-mid-1,x+mid+1);
        mpoly[k]=mpoly[ls]*mpoly[rs];
    }
    vector<int>evaluation(poly a,vector<int>x){
        a.mt();vector<int>ans;
        ans.resize(x.size());
        re(i,0,x.size())x[i]=(x[i]%mod+mod)%mod;
        if(!x.size())return ans;
        int m=x.size()-1;
        rep(i,0,m)qx[i]=x[i];
        eval_init(1,m,qx);
        evaluation(1,a,m,qx,eres);
        rep(i,0,m)ans[i]=eres[i];
        return ans;
    }
#undef rep
#undef re
#undef repd
#undef il
#undef all
#undef adm
#undef ll
#undef ls
#undef rs
}

#define MAXN 1100000
#define LL long long

const LL P=998244353;

int n,m,sizew;
vector< pair<LL,LL> > a[MAXN];
LL ans[MAXN];

void modify(int x,int cl,int cr,int l,int r,LL t1,LL t2){
    if(l<=cl && cr<=r){
        a[x].push_back(make_pair(t1,t2));
        return;
    }
    int mid=(cl+cr)>>1;
    if(l<=mid) modify(x<<1,cl,mid,l,r,t1,t2);
    if(r>mid) modify(x<<1|1,mid+1,cr,l,r,t1,t2);
}

Poly::poly getmul(int x,int l,int r){
    if(l==r){
        Poly::poly res;
        res.resiz(1);
        res[0]=a[x][l].second;
        res[1]=a[x][l].first;
        return res;
    }
    int mid=(l+r)>>1;
    Poly::poly t1=getmul(x,l,mid),t2=getmul(x,mid+1,r);
    return t1*t2;
}

void gao(int x,int cl,int cr){
    if(cl<cr){
        int mid=(cl+cr)>>1;
        gao(x<<1,cl,mid);
        gao(x<<1|1,mid+1,cr);
    }
    if(a[x].empty()) return;
    Poly::poly temp=getmul(x,0,a[x].size()-1);
    static vector<int> xs,ys;
    xs.resize(cr-cl+1);
    for(int i=cl;i<=cr;i++) xs[i-cl]=i;
    ys=Poly::evaluation(temp,xs);
    for(int i=cl;i<=cr;i++) ans[i]=ans[i]*ys[i-cl]%P;
}

int main(){
#ifdef DEBUG
    freopen("144.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    for(sizew=1;sizew<n;sizew<<=1);
    while(m--){
        int l,r;
        LL t1,t2;
        scanf("%d%d%lld%lld",&l,&r,&t2,&t1);
        t1=(t1-t2*l)%P;
        if(t1<0) t1+=P;
        modify(1,1,sizew,l,r,t2,t1);
    }
    for(int i=1;i<=n;i++) ans[i]=1;
    gao(1,1,sizew);
    for(int i=1;i<=n;i++) printf("%lld ",(ans[i]+P)%P);
}