Problem Description

"Why climb? Because the mountain is there."

On Mount Muztagh, there are $n$ points, numbered from $1$ to $n$, with point $1$ being the summit. These $n$ points form a rooted tree structure, where point $1$ is the root. For $2 \leq i \leq n$, the parent node of point $i$ is point $p_i$.

Let $d_i$ be the number of edges one needs to traverse to go from point $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 defined as a sequence starting from one of the points $2$ to $n$, making several moves to reach the summit.

A move from point $i (2 \leq i \leq n)$ can be one of the following:
1. Sprint: Within a 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 towards the summit, i.e., to the $k$-th ancestor of point $i$ in the rooted tree. It is guaranteed that $1 \leq l_i \leq r_i \leq d_i$.
2. Rest: Due to the steep terrain of Mount Muztagh, resting results in sliding down to a child node. Formally, choose a $j$ such that $p_j = i$, and move to point $j$. Notably, if point $i$ is a leaf node in the rooted tree, there is no $j$ satisfying $p_j = i$, so resting is not possible.

A climbing sequence corresponding to a climbing path is a sequence consisting of the initial point and each point reached by the moves. Formally, a climbing sequence for a path starting from point $x$ is a sequence $a_1 = x, a_2, \dots, a_m = 1$ such that for $1 \leq i < m$, $a_{i+1}$ is either the $k$-th ancestor of $a_i$ where $l_{a_i} \leq k \leq r_{a_i}$ or $p_{a_{i+1}} = a_i$.

A valid climbing path must ensure that for any point $i$ (initial or reached by a move), any subsequent point $j$ reached by a sprint must satisfy $d_j < d_i - h_i$, where $h_i$ is a given parameter, and $0 \leq h_i < d_i$. Formally, a valid 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 points $2$ to $n$, find the number of valid climbing paths starting from each point. Two climbing paths are considered different if and only if their corresponding climbing sequences are different. Since the answer may be large, output the result modulo $998,244,353$.

Input Format

This problem contains multiple test cases.

The first line of input contains an integer $c$, indicating the test point number. $c = 0$ means the test point is a sample.

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

The following lines describe each test case:

The first line of each test case contains an integer $n$, the number of points on Mount Muztagh.

The next $n-1$ lines, for $2 \leq i \leq n$, contain 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 containing $n-1$ integers, representing the number of ways to reach the summit from points $2$ to $n$, modulo $998,244,353$.

Sample Input and Output

Input Sample #1

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

Output Sample #1

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

Input Sample #2

See mountain2.in/ans
This sample meets the constraints of test points 2,3.

Output Sample #2

Input Sample #3

See mountain3.in/ans
This sample meets the constraints of test point 9.

Output Sample #3

Input Sample #4

See mountain4.in/ans
This sample meets the constraints of test points 11,12.

Output Sample #4

Input Sample #5

See mountain5.in/ans
This sample meets the constraints of test point 13.

Output Sample #5

Notes/Hints

[Sample 1 Explanation]

Sample 1 contains three test cases.

For the first test case, the structure of Mount Muztagh is as follows:

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

There are 2 valid climbing paths starting from point 4:
1. Directly sprint to the 2nd ancestor of point 4, which is the summit, with the climbing sequence $[4, 1]$.
2. Rest to point 5, then sprint to the 3rd ancestor of point 5, reaching the summit, with the climbing sequence $[4, 5, 1]$.

There are 4 valid climbing paths starting from point 5:
1. Directly sprint to the 3rd ancestor of point 5, which is the summit, with the climbing sequence $[5, 1]$.
2. Sprint to the 2nd ancestor of point 5, which is point 2, then sprint to the 1st ancestor of point 2, reaching the summit, with the climbing sequence $[5, 2, 1]$.
3. Sprint to the 2nd ancestor of point 5, which is point 2, rest to point 4, then sprint to the 2nd ancestor of point 4, reaching the summit, with the climbing sequence $[5, 2, 4, 1]$.
4. Sprint to the 2nd ancestor of point 5, which is point 2, rest to point 4, rest to point 5, then sprint to the 3rd ancestor of point 5, reaching the summit, with the climbing sequence $[5, 2, 4, 5, 1]$.

[Data Range]

For all test data, 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$.

见题面 Input 部分

见题面 Output 部分