Expected Edge Weights on Random Tree Paths

We are given a rooted tree with (n) nodes where node (1) is the root. For every node (i) ((2 \le i \le n)), its parent (f_i) is chosen uniformly at random from the interval ([l_i, r_i]) (we assume (l_i) and (r_i) satisfy (1 \le l_i \le r_i < i)). Each edge initially has weight (0).\n\nThen, there are (m) operations. The (j)th operation is described by three integers (u_j, v_j, w_j) and means that we add (w_j) to every edge on the unique simple path from node (u_j) to node (v_j). After all operations, for every node (i) with (2 \le i \le n), let the edge ((i, f_i)) be the edge connecting (i) to its parent. You are to compute the expected weight on each such edge (where the expectation is taken over all randomness in the choice of parent for every node) modulo (998,244,353).\n\nA key observation is that for a fixed edge ((i,f_i)) the edge lies on the path between two nodes (u) and (v) if and only if exactly one of (u) and (v) lies in the (random) subtree rooted at (i). Let (p_i(u)) denote the probability that node (u) is in the subtree of (i) (with the convention that for (u < i), (p_i(u)=0), and (p_i(i)=1)). By the tree generation process, for every node (u) with (u>i) we have the recurrence[ p_i(u) = \frac{\sum_{k=\max(l_u,i)}^{r_u}p_i(k)}{r_u-l_u+1}. ] Then, by linearity of expectation, the expected contribution of an operation ((u,v,w)) to edge ((i, f_i)) is[ w\Bigl(p_i(u)(1-p_i(v)) + (1-p_i(u))p_i(v)\Bigr) \quad (\text{mod }998,244,353). ]\n\nYour task is to compute for each (i=2,3,\ldots,n) the value[ \sum_{j=1}^m w_j\Bigl(p_i(u_j)(1-p_i(v_j)) + (1-p_i(u_j))p_i(v_j)\Bigr) \quad \text{mod }998,244,353. ]\n\nNote: All fractions should be handled in modular arithmetic with modulus (998,244,353) (i.e. if we need to divide by an integer, multiply by its modular inverse).

inputFormat

The first line of input contains two integers (n) and (m).\n\nThe next (n-1) lines each contain two integers (l_i) and (r_i) (for (i = 2,3,\ldots,n)).\n\nThe following (m) lines each contain three integers (u_j, v_j, w_j), describing an operation.

outputFormat

Output (n-1) space‐separated integers. The (i)th integer (for (i=2,3,\ldots,n)) should be the expected weight on the edge ((i, f_i)) modulo (998,244,353).

sample

3 1
1 1
1 2
1 3 5

499122179 5