给定一棵以 $1$ 号点为根的 $N$ 个顶点的树。我们需要为每个顶点确定一个非负整数 $a_i$。 这些 $a_i$ 必须满足以下条件：

对于所有 $1 \leq i \leq N$：

• $a_i \leq p_i$
• 设 $S_i$ 为以 $i$ 为根的子树内所有顶点 $j$ 的 $a_j$ 之和，则 $S_i \geq q_i$

对于满足上述条件的 $(a_1, a_2, \ldots, a_N)$，定义 $\sum_{i=1}^N c_{i}a_{i}$ 的最小值为 $f(c_1, c_2, \ldots, c_N)$。

求以下值对 $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)$$

输入格式

第一行包含一个整数 $N$。($1 \leq N \leq 250$)

从第二行开始的 $(N-1)$ 行，每行包含两个整数 $s_i, e_i$，表示树的一条边。($1 \leq s_i, e_i \leq N$)

对于 $1 \leq i \leq N$，第 $(N+i)$ 行包含四个整数 $p_i, q_i, L_i, R_i$。($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$)

保证给定的图是一棵树，且输入保证至少存在一组满足条件的 $(a_1, a_2, \ldots, a_N)$。

输出格式

输出题目所求的值对 $998\,244\,353$ 取模的结果。$998\,244\,353 = 119 \times 2^{23} + 1$ 是一个质数。

样例

输入格式 1

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

输出格式 1

14

输入格式 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

输出格式 2

39072

说明

顶点 $j$ 包含在顶点 $i$ 的子树内，意味着 $j=i$ 或者顶点 $i$ 是顶点 $j$ 的祖先。