Problem Description

In JOI Kingdom, there are $N$ cities numbered from $1$ to $N$. There are $N - 1$ bidirectional roads numbered from $1$ to $N - 1$. The $i$-th road connects city $A_i$ and city $B_i$.

Some roads in JOI Kingdom have checkpoints. There are $M$ checkpoints numbered from $1$ to $M$. The $j$-th checkpoint is located on road $P_j$. To pass through this checkpoint, one needs to pay either 1 gold coin or $C_j$ silver coins.

There are $Q$ citizens numbered from $1$ to $Q$. The $k$-th citizen has $X_k$ gold coins and $Y_k$ silver coins and wants to travel from city $S_k$ to city $T_k$. Since gold coins are valuable, all citizens want to keep as many gold coins as possible.

Write a program that, given information about the cities, roads, checkpoints, and citizens in JOI Kingdom, determines for each $k (1 \le k \le Q)$ whether citizen $k$ can travel from city $S_k$ to city $T_k$, and if possible, calculates the maximum number of gold coins citizen $k$ can keep.

Input Format

Read the following data from the standard input:

$N \ M \ Q$

$A_1 \ B_1$

$A_2 \ B_2$

$\vdots$

$A_{N - 1} \ B_{N - 1}$

$P_1 \ C_1$

$P_2 \ C_2$

$\vdots$

$P_M \ C_M$

$S_1 \ T_1 \ X_1 \ Y_1$

$S_2 \ T_2 \ X_2 \ Y_2$

$\vdots$

$S_Q \ T_Q \ X_Q \ Y_Q$

Output Format

Write $Q$ lines to the standard output. In the $k$-th line $(1 \le k \le Q)$, if citizen $k$ can travel from city $S_k$ to city $T_k$, output the maximum number of gold coins citizen $k$ can keep. Otherwise, output $-1$.

Sample Input and Output

Sample Input #1

5 4 3
1 2
1 3
2 4
2 5
2 9
2 4
3 5
4 7
3 4 2 11
5 3 4 5
2 3 1 1

Sample Output #1

1
2
-1

Sample Input #2

10 7 9
1 8
6 3
5 9
7 9
3 1
3 4
10 1
2 6
5 6
9 4
7 4
7 4
2 4
7 4
7 4
1 4
8 6 5 3
3 9 8 0
4 7 6 15
7 4 9 3
6 4 8 0
9 10 5 16
5 3 2 4
2 8 4 3
6 1 3 3

Sample Output #2

3
6
6
7
7
3
1
2
2

Sample Input #3

8 7 11
1 2
2 3
3 4
4 5
5 6
6 7
7 8
4 4
3 7
2 10
5 2
4 1
4 4
5 6
6 3 7 69
7 1 5 55
3 1 6 8
8 2 5 45
4 6 4 45
6 1 3 33
2 1 0 19
3 7 2 31
7 1 2 31
7 2 4 58
8 3 5 63

Sample Output #3

7
5
5
5
4
2
0
2
1
4
5

Sample Input #4

8 7 11
1 8
1 4
3 1
3 6
6 7
2 1
5 2
5 5
5 8
4 7
6 6
4 1
6 4
1 7
4 7 2 18
2 4 5 1
4 2 1 32
1 5 7 21
2 5 0 50
8 4 4 33
1 7 6 16
4 8 7 18
1 2 8 13
5 4 10 42
7 1 6 40

Sample Output #4

1
3
1
7
0
4
5
7
8
10
6

Notes/Hints

Sample Explanation #1

Citizen $1$ can travel from city $3$ to city $4$ as follows. After the travel, citizen $1$ keeps one gold coin.

1. Citizen $1$ travels from city $3$ to city $1$ via road $2$. There are checkpoints $1, 2$ on road $2$. Citizen $1$ pays one gold coin at checkpoint $1$ and four silver coins at checkpoint $2$, respectively. After that, citizen $1$ keeps one gold coin and seven silver coins.
2. Citizen $1$ travels from city $1$ to city $2$ via road $1$. Since there is no checkpoint on road $1$, citizen $1$ keeps one gold coin and seven silver coins.
3. Citizen $1$ travels from city $2$ to city $4$ via road $3$. There is checkpoint $3$ on road $3$. Citizen $1$ pays five silver coins at checkpoint $3$. After that, citizen $1$ keeps one gold coin and two silver coins.

Since it is impossible for citizen $1$ to travel by finally keeping more than or equal to two gold coins, output $1$ in the first line.

Citizen $2$ can travel from city $5$ to city $3$ as follows. After the travel, citizen $2$ keeps two gold coins.

1. Citizen $2$ travels from city $5$ to city $2$ via road $4$. There is checkpoint $4$ on road $4$. Citizen $2$ pays one gold coin at checkpoint $4$. After that, citizen $2$ keeps three gold coins and five silver coins.
2. Citizen $2$ travels from city $2$ to city $1$ via road $1$. Since there is no checkpoint on road $1$, citizen $2$ keeps three gold coins and five silver coins.
3. Citizen $2$ travels from city $1$ to city $3$ via road $2$. On road $2$, there are checkpoints $1, 2$. Citizen $2$ pays one gold coin at checkpoint $1$ and four silver coins at checkpoint $2$, respectively. After that, citizen $2$ keeps two gold coins and one silver coin.

Since it is impossible for citizen $2$ to travel by finally keeping more than or equal to three gold coins, output $2$ in the second line.

Since it is impossible for citizen $3$ to travel from city $2$ to city $3$, output $-1$ in the third line.

This sample satisfies the constraints of subtasks $1, 4$.

Sample Explanation #2

This sample satisfies the constraints of subtasks $1, 2, 4$.

Sample Explanation #3

This sample satisfies the constraints of subtasks $1, 3, 4$.

Sample Explanation #4

This sample satisfies the constraints of subtasks $1, 4$.

Data Range

For all test data, the following conditions hold:
- $2 \le N \le 10^5$
- $1 \le M, Q \le 10^5$
- $1 \le A_i, B_i \le N$
- $1 \le P_j \le N - 1$
- $1 \le C_j \le 10^9$
- $1 \le S_k, T_k \le N$
- $S_k \ne T_k$
- $0 \le X_k \le 10^9$
- $0 \le Y_k \le 10^{18}$
- The given roads ensure all cities are connected.
- All inputs are integers.

见题面 Input 部分

见题面 Output 部分