记录编号	611813	评测结果	AAAAAAAAAA
题目名称	时空跳跃	最终得分	100
用户昵称	RpUtl	是否通过	通过
代码语言	C++	运行时间	0.720 s
提交时间	2026-02-04 20:57:20	内存使用	19.55 MiB

//Date: 2024-08-15 13:12:20
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int rd() {
    int s=0,m=0;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-')m=1;ch=getchar();}
    while( isdigit(ch)) s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return m?-s:s;
}
bool MBE;
namespace SOLVER {
const int M=998244353;
int qpow(int x,int y=M-2,int mod=M) {int s=1;for(;y;y>>=1,x=x*x%mod) if(y&1) s=s*x%mod;return s;}
int n,m,inv[5005],l[5005],r[5005],a[5005][5005],ans[5005];
void MAIN() {
    inv[1]=1;for(int i=2;i<=5000;i++) inv[i]=(M-M/i*inv[M%i]%M)%M;
    cin>>n;for(int i=2;i<=n;i++) l[i]=rd(),r[i]=rd();
    cin>>m;
    for(int i=1,u,v,w;i<=m;i++) {
        u=rd(),v=rd(),w=rd();
        if(u>v) swap(u,v);
        a[u][v]+=w,a[u-1][v]-=w,a[u][v-1]-=w,a[u-1][v-1]+=w;
    }
    for(int i=n;i>=2;i--) {
        for(int j=n;j>=1;j--) a[j][i]+=a[j+1][i]+a[j][i+1]-a[j+1][i+1]+M,a[j][i]%=M;
        for(int j=1;j<i;j++) {
            ans[i]+=a[j][i],ans[i]%=M;int ww=a[j][i]*inv[r[i]-l[i]+1]%M;
            if(l[i]<=j) {
                int R=min(j,r[i]);
                a[R][j]=(a[R][j]+ww)%M,a[R][j-1]=(a[R][j-1]-ww+M)%M;
                a[l[i]-1][j]=(a[l[i]-1][j]-ww+M)%M,a[l[i]-1][j-1]=(a[l[i]-1][j-1]+ww)%M;
            }
            if(r[i]>j) {
                int L=max(j+1,l[i]);
                a[j][r[i]]=(a[j][r[i]]+ww)%M,a[j-1][r[i]]=(a[j-1][r[i]]-ww+M)%M;
                a[j][L-1]=(a[j][L-1]-ww+M)%M,a[j-1][L-1]=(a[j-1][L-1]+ww)%M;
            }
        }
    }
    for(int i=2;i<=n;i++) cout<<ans[i]<<' ';
}
}
bool MED;
signed main() {
	freopen("timejump.in","r",stdin);
	freopen("timejump.out","w",stdout);
    //freopen(".in","r",stdin);freopen(".out","w",stdout);
    for(int tt=1;tt;tt--) SOLVER::MAIN();
    return 0;
}