题目描述

给定一棵以顶点 $1$ 为根、包含 $N$ 个顶点的树。你需要为每个顶点确定一个非负整数 $a_i$。

这些数必须满足以下条件。对于每个 $1\le i\le N$：

• $a_i\le p_i$；
• 设 $S_i$ 为顶点 $i$ 的子树内所有顶点 $j$ 的 $a_j$ 之和，则 $S_i\ge q_i$。

对于给定的系数 $(c_1,c_2,\ldots,c_N)$，定义

$$f(c_1,c_2,\ldots,c_N) = \min \sum_{i=1}^{N} c_i a_i,$$

其中最小值在所有满足上述条件的 $(a_1,a_2,\ldots,a_N)$ 上取得。

请计算

$$\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,\ldots,c_N)$$

对 $998244353$ 取模后的结果。

输入格式

第一行输入一个整数 $N$。

$$1\le N\le 250.$$

接下来 $N-1$ 行，每行输入两个整数 $s_i,e_i$，表示树中存在一条连接 $s_i$ 与 $e_i$ 的边。

随后 $N$ 行，第 $i$ 行输入四个整数 $p_i,q_i,L_i,R_i$。

$$1\le L_i\le R_i\le 250, \qquad 0\le p_i,q_i\le 250,$$

并保证

$$\sum_{i=1}^{N}p_i\le 250.$$

输入图保证是一棵树，并且至少存在一组满足所有约束的 $(a_1,a_2,\ldots,a_N)$。

输出格式

输出题目所求值对 $998244353$ 取模后的结果。

其中

$$998244353=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

输出

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

输出

39072

说明

顶点 $j$ 位于顶点 $i$ 的子树内，当且仅当 $j=i$，或者顶点 $i$ 是顶点 $j$ 的祖先。