Cho một cây có $N$ đỉnh với đỉnh $1$ là gốc. Chúng ta cần chọn các số nguyên không âm $a_i$ cho mỗi đỉnh. Các giá trị $a_i$ phải thỏa mãn các điều kiện sau:

Với mọi $1 \leq i \leq N$:

• $a_i \leq p_i$
• Gọi $S_i$ là tổng các giá trị $a_j$ của tất cả các đỉnh $j$ nằm trong cây con của đỉnh $i$, ta có $S_i \geq q_i$

Với bộ $(a_1, a_2, \ldots, a_N)$ thỏa mãn các điều kiện trên, ta định nghĩa $f(c_1, c_2, \ldots, c_N)$ là giá trị nhỏ nhất của $\sum_{i=1}^N c_{i}a_{i}$.

Hãy tính giá trị sau theo 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)$$

Dữ liệu vào

Dòng đầu tiên chứa số lượng đỉnh $N$ ($1 \leq N \leq 250$).

Từ dòng thứ hai, $(N-1)$ dòng tiếp theo chứa thông tin về các cạnh của cây. Dòng thứ $i$ trong số này chứa hai số nguyên $s_i, e_i$ cách nhau bởi dấu cách ($1 \leq s_i, e_i \leq N$), biểu thị sự tồn tại của một cạnh nối giữa $s_i$ và $e_i$.

Với mỗi $1 \leq i \leq N$, dòng thứ $(N+i)$ chứa các số $p_i, q_i, L_i, R_i$ cách nhau bởi dấu cách ($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$).

Đồ thị đã cho là một cây và chỉ các đầu vào đảm bảo tồn tại bộ $(a_1, a_2, \ldots, a_N)$ thỏa mãn các điều kiện mới được đưa ra.

Dữ liệu ra

In ra giá trị của biểu thức đã cho theo modulo $998\,244\,353$. $998\,244\,353 = 119 \times 2^{23} + 1$ là một số nguyên tố.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

14

Dữ liệu vào 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

Dữ liệu ra 2

39072

Ghi chú

Đỉnh $j$ nằm trong cây con của đỉnh $i$ nghĩa là $j=i$ hoặc đỉnh $i$ là tổ tiên của đỉnh $j$.