Дан ориентированный на корень в вершине $1$ граф, являющийся деревом с $N$ вершинами. Мы должны выбрать неотрицательные целые числа $a_i$ для каждой вершины.

При этом значения $a_i$ должны удовлетворять следующим условиям:

Для всех $1 \leq i \leq N$:

• $a_i \leq p_i$
• Пусть $S_i$ — сумма значений $a_j$ для всех вершин $j$, принадлежащих поддереву вершины $i$. Тогда $S_i \geq q_i$

Определим $f(c_1, c_2, \ldots, c_N)$ как минимальное значение $\sum_{i=1}^N c_{i}a_{i}$ для набора $(a_1, a_2, \ldots, a_N)$, удовлетворяющего вышеуказанным условиям.

Найдите значение следующей суммы по модулю $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)$$

Входные данные

В первой строке дано количество вершин $N$ ($1 \leq N \leq 250$).

Со второй строки и далее в течение $(N-1)$ строк приводится информация о ребрах дерева. В $i$-й из этих строк через пробел записаны два целых числа $s_i$ и $e_i$ ($1 \leq s_i, e_i \leq N$), означающие наличие ребра между $s_i$ и $e_i$.

Для каждого $1 \leq i \leq N$ в $(N+i)$-й строке через пробел даны $p_i$, $q_i$, $L_i$, $R_i$ ($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$).

Гарантируется, что заданный граф является деревом и что для входных данных всегда существует хотя бы один набор $(a_1, a_2, \ldots, a_N)$, удовлетворяющий заданным условиям.

Выходные данные

Выведите значение, указанное в условии задачи, по модулю $998\,244\,353$. Число $998\,244\,353 = 119 \times 2^{23} + 1$ является простым.

Примеры

Входные данные 1

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

Выходные данные 1

14

Входные данные 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

Выходные данные 2

39072

Примечание

Вершина $j$ содержится в поддереве вершины $i$, если $j=i$ или если вершина $i$ является предком вершины $j$.