$\prod_{i=1}^N(R_i-L_i+1)$ Trees

A tree with $N$ vertices rooted at vertex 1 is given. Assign a nonnegative integer $a_i$ to each vertex $i$.

The values $a_i$ must satisfy the following two conditions for every $1 \le i \le N$.

• $a_i \le p_i$
• Let $S_i$ be the sum of $a_j$ over all vertices $j$ in the subtree of vertex $i$. Then $S_i \ge q_i$.

For each $(a_1, a_2, \ldots, a_N)$ that satisfies these conditions, let $f(c_1, c_2, \ldots, c_N)$ be the minimum value of $\sum_{i=1}^N c_i a_i$.

Find the following value 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)$

The first line contains $N$, the number of vertices ($1 \le N \le 250$).

Each of the next $N-1$ lines contains two integers $s_i$ and $e_i$ separated by a space, meaning there is an edge between $s_i$ and $e_i$. ($1 \le s_i, e_i \le N$)

For each $1 \le i \le N$, the $(N+i)$-th line contains $p_i$, $q_i$, $L_i$, and $R_i$ separated by spaces. ($1 \le L_i \le R_i \le 250$; $0 \le p_i, q_i \le 250$; $\sum_{i=1}^N p_i \le 250$)

The given graph is a tree, and only inputs where a valid $(a_1, a_2, \ldots, a_N)$ exists are given.

Print the value from the statement modulo $998\,244\,353$. Note that $998\,244\,353=119\times 2^{23}+1$ is prime.

Vertex $j$ is in the subtree of vertex $i$ if and only if $j=i$ or vertex $i$ is an ancestor of vertex $j$.