給定一棵有 $N$ 個頂點的樹，以頂點 $1$ 為根。我們需要為每個頂點指定一個非負整數 $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)$，定義 $f(c_1, c_2, \ldots, c_N)$ 為 $\sum_{i=1}^N c_{i}a_{i}$ 的最小值。

請計算以下數值對 $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)$ 行描述樹的邊，第 $i$ 行包含兩個整數 $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$ 的祖先。