Dane jest drzewo o $N$ wierzchołkach, którego korzeniem jest wierzchołek $1$. Musimy przypisać każdemu wierzchołkowi nieujemną liczbę całkowitą $a_i$. Wartości $a_i$ muszą spełniać następujące warunki:

Dla każdego $1 \leq i \leq N$:

• $a_i \leq p_i$
• Niech $S_i$ będzie sumą wartości $a_j$ dla wszystkich wierzchołków $j$ znajdujących się w poddrzewie wierzchołka $i$. Wtedy $S_i \geq q_i$.

Zdefiniujmy $f(c_1, c_2, \ldots, c_N)$ jako minimalną wartość $\sum_{i=1}^N c_{i}a_{i}$ dla ciągu $(a_1, a_2, \ldots, a_N)$ spełniającego powyższe warunki.

Oblicz sumę:

$$\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)$$

Wynik podaj modulo $998\,244\,353$.

Wejście

W pierwszej linii podana jest liczba wierzchołków $N$ ($1 \leq N \leq 250$).

W kolejnych $(N-1)$ liniach podane są informacje o krawędziach drzewa. W $i$-tej z tych linii znajdują się dwie liczby całkowite $s_i$ oraz $e_i$ oddzielone spacją ($1 \leq s_i, e_i \leq N$), oznaczające istnienie krawędzi między $s_i$ a $e_i$.

Dla każdego $1 \leq i \leq N$, w $(N+i)$-tej linii podane są liczby $p_i$, $q_i$, $L_i$, $R_i$ oddzielone spacjami ($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$).

Podany graf jest drzewem. Dane wejściowe gwarantują, że istnieje co najmniej jeden ciąg $(a_1, a_2, \ldots, a_N)$ spełniający podane warunki.

Wyjście

Wypisz wartość sumy modulo $998\,244\,353$. Liczba $998\,244\,353 = 119 \times 2^{23} + 1$ jest liczbą pierwszą.

Przykład

Wejście 1

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

Wyjście 1

14

Wejście 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

Wyjście 2

39072

Uwagi

Wierzchołek $j$ znajduje się w poddrzewie wierzchołka $i$, jeśli $j=i$ lub wierzchołek $i$ jest przodkiem wierzchołka $j$.