Problem Background

The person downstairs is right, but sszcdjr cleverly outdid my brute force tree partition in NOI 2024 D2T2.

The person upstairs is right, but tree chain partition got me a perfect score, so I created this problem to express my love for tree chain partition.

Problem Description

Given a rooted tree with $n$ nodes where node $1$ is the root. For each node $2 \leq i \leq n$, its parent $f_i$ is uniformly randomly chosen from the interval $[l_i, r_i]$. Each edge in the tree has an initial weight of $0$.

There are $m$ operations. The $i$-th operation indicates adding $w_i$ to the weights of all edges on the path from $u_i$ to $v_i$. After all $m$ operations, for each $i = 2 \sim n$, find the expected weight of the edge $(i, f_i)$, modulo $998244353$.

Input Format

The first line contains a positive integer $n$.

The next $n-1$ lines, where the $i$-th line contains two positive integers $l_{i+1}$ and $r_{i+1}$.

The next line contains a positive integer $m$.

The next $m$ lines, where the $i$-th line contains three positive integers $u_i$, $v_i$, and $w_i$.

Output Format

One line with $n-1$ positive integers, where the $i$-th integer represents the expected weight of the edge $(i+1, f_{i+1})$, modulo $998244353$.

Sample Input and Output

Sample Input #1

3
1 1
1 2
1
1 3 2

Sample Output #1

1 2

Sample Input #2

5
1 1
1 2
3 3
2 4
9
2 5 497855355
1 5 840823564
3 1 295265328
2 3 457999227
4 4 235621825
2 1 86836399
5 2 800390742
5 3 869167938
2 4 269250165

Sample Output #2

405260353 409046983 606499796 13504540

Notes

Sample Explanation 1

There are two possible scenarios for the parents of the nodes:

• $f_2 = 1, f_3 = 1$, where the weights of edges $(f_2, 2)$ and $(f_3, 3)$ are $0$ and $2$ respectively.

• $f_2 = 1, f_3 = 2$, where the weights of edges $(f_2, 2)$ and $(f_3, 3)$ are $2$ and $2$ respectively.

Thus, the expected weight of edge $(f_2, 2)$ is $\frac{0+2}{2} = 1$, and the expected weight of edge $(f_3, 3)$ is $\frac{2+2}{2} = 2$.

Data Size and Constraints

This problem uses batched testing.

For all data, it is guaranteed that $1 \leq n, m \leq 5000$, $1 \leq l_i \leq r_i < i$, $1 \leq u_i, v_i \leq n$, and $1 \leq w_i \leq 10^9$.

见题面 Input 部分

见题面 Output 部分