Problem Description

"Why climb? Because the mountain is there."

There are $n$ locations on Muztagh Mountain, numbered from $1$ to $n$, where location $1$ is the summit. These $n$ locations form a rooted tree, with node $1$ as the root. For $2\leq i\leq n$, the parent of node $i$ is node $p_i$.

Let $d_i$ be the number of edges on the path from node $i$ to the summit. Formally, $d_1=0$, and for $2\leq i\leq n$, $d_i=d_{p_i}+1$.

A climbing path is a plan that starts from some node among $2\sim n$, and after several moves, reaches the summit.

A move starting from node $i(2\leq i\leq n)$ is one of the following two types:

1. Sprint: within the given sprint range $[l_i,r_i]$, choose a positive integer $k$ such that $l_i\leq k\leq r_i$, and move $k$ steps toward the summit, i.e. move to the $k$-th ancestor of node $i$ in the rooted tree. It is guaranteed that $1\leq l_i\leq r_i\leq d_i$.
2. Rest: because the terrain of Muztagh Mountain is steep, when resting you will slip down to one of its children. Formally, choose a node $j$ such that $p_j=i$, and move to node $j$. In particular, if node $i$ is a leaf in the rooted tree, then there is no $j$ satisfying $p_j=i$, so you cannot choose Rest in this case.

The climbing sequence corresponding to a climbing path is the sequence consisting of the starting node and every node reached after each move. Formally, the climbing sequence corresponding to a climbing path starting from node $x$ is a node sequence $a_1=x,a_2,\dots,a_m=1$ such that for $1\leq i<m$, $a_{i+1}$ is either the $k(l_{a_i}\leq k\leq r_{a_i})$-th ancestor of $a_i$, or satisfies $p_{a_{i+1}}=a_i$.

To ensure that every sprint can get closer to the summit, a legal climbing path must satisfy: for the starting node or any node $i$ reached after some move, every later node $j$ reached by sprinting must satisfy $d_j<d_i-h_i$, where $h_i$ is a given parameter, guaranteed to satisfy $0\leq h_i<d_i$. Formally, a legal climbing path with climbing sequence $a_1,a_2,\dots,a_m$ must satisfy: for all $1\leq i<j\leq m$, if $p_{a_j} \neq a_{j-1}$, then $d_{a_j}<d_{a_i}-h_{a_i}$.

For all nodes $2\sim n$, find the number of legal climbing paths starting from each of these nodes. Two climbing paths are different if and only if their corresponding climbing sequences are different. Since the answer may be large, you only need to output it modulo $998\,244\,353$.

Input Format

This problem contains multiple test cases.

The first line contains an integer $c$, indicating the test point ID. $c=0$ means this test point is the sample.

The second line contains an integer $t$, the number of test cases.

Then each test case is given as follows:

The first line contains an integer $n$, the number of locations on Muztagh Mountain.

The next $n-1$ lines: the $(i-1)$-th line ($2\leq i\leq n$) contains four integers $p_i,l_i,r_i,h_i$. It is guaranteed that $1\leq p_i<i$, $1\leq l_i\leq r_i\leq d_i$, and $0\leq h_i<d_i$.

Output Format

For each test case, output one line with $n-1$ integers, where the $i$-th integer is the number of ways (modulo $998\,244\,353$) to reach the summit starting from node $i+1$ (i.e. nodes $2\sim n$).

0
3
5
1 1 1 0
2 1 1 0
2 1 2 1
4 2 3 0
6
1 1 1 0
2 1 2 0
3 1 3 2
4 1 4 1
5 1 5 3
6
1 1 1 0
2 1 2 0
2 1 2 0
3 1 2 0
3 2 3 2

3 3 2 4
5 9 3 21 6
4 10 5 14 1

见 mountain2.in/ans
这个样例满足测试点 2,3 的约束条件

见 mountain3.in/ans
这个样例满足测试点 9 的约束条件

见 mountain4.in/ans
这个样例满足测试点 11,12 的约束条件

见 mountain5.in/ans
这个样例满足测试点 13 的约束条件

Hint

[Sample 1 Explanation]

Sample $1$ contains three test cases.

For the first test case, the structure of locations on Muztagh Mountain is as follows:

In this test case, $d_1=0$, $d_2=1$, $d_3=d_4=2$, $d_5=3$.

There are $2$ legal climbing paths starting from $4$:

1. Sprint directly to the 2-nd ancestor of $4$, i.e. $1$, reaching the summit. The corresponding climbing sequence is $[4,1]$.
2. Rest first and slip down to $5$, then sprint from $5$ to its 3-rd ancestor, reaching the summit. The corresponding climbing sequence is $[4,5,1]$.

There are $4$ legal climbing paths starting from $5$:

1. Sprint directly to the 3-rd ancestor of $5$, i.e. $1$, reaching the summit. The corresponding climbing sequence is $[5,1]$.
2. Sprint first to the 2-nd ancestor of $5$, i.e. $2$; then sprint from $2$ to its 1-st ancestor, reaching the summit. The corresponding climbing sequence is $[5,2,1]$.
3. Sprint first to the 2-nd ancestor of $5$, i.e. $2$; then rest at $2$ and slip down to $4$; then sprint from $4$ to its 2-nd ancestor, reaching the summit. The corresponding climbing sequence is $[5,2,4,1]$.
4. Sprint first to the 2-nd ancestor of $5$, i.e. $2$; then rest at $2$ and slip down to $4$; keep resting and slip down to $5$; then sprint again from $5$ to its 3-rd ancestor, reaching the summit. The corresponding climbing sequence is $[5,2,4,5,1]$.

[Constraints]

For all test cases, it is guaranteed that: $1\leq t\leq 4$, $2\leq n\leq 10^5$.

For any $2\leq i\leq n$, it is guaranteed that: $1\leq p_i<i$, $1\leq l_i\leq r_i\leq d_i$, $0\leq h_i<d_i$.

::cute-table{tuack}

Translated by ChatGPT 5