A tree with $N$ vertices rooted at vertex $1$ is given. We are to assign a non-negative integer $a_i$ to each vertex. These $a_i$ must satisfy the following conditions:

For all $1 \leq i \leq N$,

• $a_i \leq p_i$
• Let $S_i$ be the sum of $a_j$ for all vertices $j$ in the subtree of $i$. Then $S_i \geq q_i$.

Let $f(c_1, c_2, \ldots, c_N)$ be the minimum value of $\sum_{i=1}^N c_{i}a_{i}$ for a given $(a_1, a_2, \ldots, a_N)$ satisfying the conditions above.

Calculate the following value modulo $998\,244\,353$:

$$\sum_{c_1=L_1}^{R_1} \sum_{c_2=L_2}^{R_2} \cdots \sum_{c_N=L_N}^{R_N} f(c_1, c_2, \cdots, c_N)$$

Input

The first line contains the number of vertices $N$. ($1 \leq N \leq 250$)

The next $(N-1)$ lines contain information about the tree edges. The $i$-th line contains two space-separated integers $s_i$ and $e_i$. ($1 \leq s_i, e_i \leq N$) This indicates that there is an edge between $s_i$ and $e_i$.

For $1 \leq i \leq N$, the $(i+1)$-th line contains $p_i$, $q_i$, $L_i$, and $R_i$ separated by spaces. ($1 \leq L_i \leq R_i \leq 250$; $0 \leq p_i, q_i \leq 250$; $\sum_{i=1}^N p_i \leq 250$)

The given graph is a tree, and only inputs where there exists at least one $(a_1, a_2, \ldots, a_N)$ satisfying the given conditions are provided.

Output

Output the value given in the problem modulo $998\,244\,353$. $998\,244\,353 = 119 \times 2^{23} + 1$ is a prime number.

Examples

Input 1

4
1 2
1 3
1 4
2 5 5 5
1 1 2 2
2 1 3 3
1 1 1 1

Output 1

14

Input 2

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

Output 2

39072

Note

A vertex $j$ is contained in the subtree of vertex $i$ if $j=i$ or if vertex $i$ is an ancestor of vertex $j$.