Se da un árbol de $N$ vértices con el vértice $1$ como raíz. Debemos asignar un entero no negativo $a_i$ a cada vértice. En este caso, los $a_i$ deben satisfacer las siguientes condiciones.

Para todo $1 \leq i \leq N$:

• $a_i \leq p_i$
• Sea $S_i$ la suma de los valores $a_j$ para todos los vértices $j$ dentro del subárbol del vértice $i$. Entonces, $S_i \geq q_i$.

Definamos $f(c_1, c_2, \ldots, c_N)$ como el valor mínimo de $\sum_{i=1}^N c_{i}a_{i}$ para una tupla $(a_1, a_2, \ldots, a_N)$ que satisfaga las condiciones anteriores.

Calcula el siguiente valor módulo $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)$$

Entrada

La primera línea contiene el número de vértices $N$. ($1 \leq N \leq 250$)

Desde la segunda línea, se proporciona información sobre las aristas del árbol en $(N-1)$ líneas. La $i$-ésima línea contiene dos enteros $s_i$ y $e_i$ separados por un espacio. ($1 \leq s_i, e_i \leq N$) Esto indica que existe una arista entre $s_i$ y $e_i$.

Para $1 \leq i \leq N$, la línea $(N+i)$ contiene $p_i$, $q_i$, $L_i$ y $R_i$ separados por espacios. ($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$)

El grafo dado forma un árbol, y solo se proporcionan entradas para las cuales existe al menos una tupla $(a_1, a_2, \ldots, a_N)$ que satisface las condiciones dadas.

Salida

Imprime el valor dado en el problema módulo $998\,244\,353$. $998\,244\,353 = 119 \times 2^{23} + 1$ es un número primo.

Ejemplos

Entrada 1

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

Salida 1

14

Entrada 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

Salida 2

39072

Nota

Que el vértice $j$ esté contenido dentro del subárbol del vértice $i$ significa que $j=i$ o que el vértice $i$ es un ancestro del vértice $j$.