$1$번 정점을 루트로 하는 정점 $N$개의 트리가 주어진다. 우리는 각 정점에 쓰일 음이 아닌 정수 $a_i$를 정할 것이다. 이때 $a_i$들은 다음 조건을 만족해야 한다.

모든 $1 \leq i \leq N$에 대해서,

• $a_i \leq p_i$
• $i$번 서브트리 내부의 정점 $j$에 대해서 $a_j$를 모두 더한 값을 $S_i$라고 했을 때, $S_i \geq q_i$

위의 조건을 만족하는 $(a_1, a_2, \ldots, a_N)$에 대해 $\sum_{i=1}^N c_{i}a_{i}$의 최솟값을 $f(c_1, c_2, \ldots, c_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)$$

Input

첫 줄에 정점의 개수 $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)$이 존재하는 입력만이 주어진다.

Output

문제에 주어진 값을 $998\,244\,353$으로 나눈 나머지를 출력한다. $998\,244\,353 = 119 \times 2^{23} + 1$은 소수이다.

Examples

Input 1

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

Output 1

14

Input 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

Output 2

39072

Note

$j$번 정점이 $i$번 서브트리 내부에 포함된다는 것은 $j=i$이거나 $i$번 정점이 $j$번 정점의 조상이라는 것이다.