On nous donne un arbre à $N$ sommets enraciné au sommet $1$. Nous devons choisir des entiers non négatifs $a_i$ pour chaque sommet. Ces $a_i$ doivent satisfaire les conditions suivantes.

Pour tout $1 \leq i \leq N$ :

• $a_i \leq p_i$
• Soit $S_i$ la somme des $a_j$ pour tous les sommets $j$ situés dans le sous-arbre du sommet $i$. Alors, $S_i \geq q_i$

Soit $f(c_1, c_2, \ldots, c_N)$ la valeur minimale de $\sum_{i=1}^N c_{i}a_{i}$ pour un $(a_1, a_2, \ldots, a_N)$ satisfaisant les conditions ci-dessus.

Calculez la valeur suivante 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)$$

Entrée

La première ligne contient le nombre de sommets $N$. ($1 \leq N \leq 250$)

Les $(N-1)$ lignes suivantes décrivent les arêtes de l'arbre. La $i$-ième ligne contient deux entiers $s_i$ et $e_i$ séparés par un espace. ($1 \leq s_i, e_i \leq N$) Cela signifie qu'il existe une arête entre $s_i$ et $e_i$.

Pour $1 \leq i \leq N$, la $(N+i)$-ième ligne contient $p_i$, $q_i$, $L_i$ et $R_i$ séparés par des espaces. ($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$)

Le graphe donné est un arbre, et seules les entrées pour lesquelles il existe au moins un $(a_1, a_2, \ldots, a_N)$ satisfaisant les conditions sont données.

Sortie

Affichez la valeur donnée dans le problème modulo $998\,244\,353$. $998\,244\,353 = 119 \times 2^{23} + 1$ est un nombre premier.

Exemples

Entrée 1

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

Sortie 1

14

Entrée 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

Sortie 2

39072

Remarque

Le fait qu'un sommet $j$ soit inclus dans le sous-arbre du sommet $i$ signifie que $j=i$ ou que le sommet $i$ est un ancêtre du sommet $j$.