頂点 $1$ を根とする $N$ 個の頂点からなる木が与えられる。各頂点に割り当てる非負整数 $a_i$ を決定する。 このとき、$a_i$ は以下の条件を満たさなければならない。

すべての $1 \leq i \leq N$ に対して、

• $a_i \leq p_i$
• 頂点 $i$ を根とする部分木に含まれるすべての頂点 $j$ について、$a_j$ の総和を $S_i$ としたとき、$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)$$

入力

1行目に頂点数 $N$ が与えられる。($1 \leq N \leq 250$)

2行目から $(N-1)$ 行にわたって、木の辺の情報が与えられる。$i$ 番目の行には、2つの整数 $s_i, e_i$ が空白区切りで与えられる。($1 \leq s_i, e_i \leq N$) これは $s_i$ と $e_i$ を結ぶ辺が存在することを意味する。

$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$ の祖先であることを指す。