JOI 王国共有 $N$ 座城市，编号为 $1$ 到 $N$。JOI 王国共有 $N-1$ 条道路，编号为 $1$ 到 $N-1$。第 $i$ 条道路（$1 \le i \le N-1$）连接城市 $A_i$ 和城市 $B_i$，且是双向的。通过这些道路，可以从任意城市到达其他任意城市。

JOI 王国的某些道路上设有检查站。共有 $M$ 个检查站，编号为 $1$ 到 $M$。第 $j$ 个检查站（$1 \le j \le M$）位于第 $P_j$ 条道路上。通过该检查站时，需要支付一枚金币或 $C_j$ 枚银币。

JOI 王国共有 $Q$ 名市民，编号为 $1$ 到 $Q$。第 $k$ 名市民（$1 \le k \le Q$）拥有 $X_k$ 枚金币和 $Y_k$ 枚银币，想要从城市 $S_k$ 前往城市 $T_k$。由于金币非常珍贵，所有市民都希望尽可能多地保留金币。

请编写一个程序，在给定 JOI 王国的城市、道路、检查站以及市民信息的情况下，对于每名市民 $k$（$1 \le k \le Q$），判断其是否能够从城市 $S_k$ 前往城市 $T_k$。如果可以，计算该市民能够保留的金币的最大数量。

输入格式

从标准输入读取以下数据：

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

输出格式

输出 $Q$ 行。第 $k$ 行（$1 \le k \le Q$）中，如果市民 $k$ 可以从城市 $S_k$ 前往城市 $T_k$，则输出该市民能够保留的金币的最大数量。否则，输出 $-1$。

数据范围

• $2 \le N \le 100\,000$
• $1 \le M \le 100\,000$
• $1 \le Q \le 100\,000$
• $1 \le A_i \le N$ ($1 \le i \le N-1$)
• $1 \le B_i \le N$ ($1 \le i \le N-1$)
• 保证图连通。
• $1 \le P_j \le N-1$ ($1 \le j \le M$)
• $1 \le C_j \le 10^9$ ($1 \le j \le M$)
• $1 \le S_k \le N$ ($1 \le k \le Q$)
• $1 \le T_k \le N$ ($1 \le k \le Q$)
• $S_k \neq T_k$ ($1 \le k \le Q$)
• $0 \le X_k \le 10^9$ ($1 \le k \le Q$)
• $0 \le Y_k \le 10^{18}$ ($1 \le k \le Q$)
• 输入均为整数。

子任务

1. (10 分) $N \le 2\,000, M \le 2\,000, Q \le 2\,000$
2. (28 分) $C_1 = C_2 = \dots = C_M$
3. (30 分) $A_i = i, B_i = i+1$ ($1 \le i \le N-1$)
4. (32 分) 无附加限制。

样例

样例输入 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

样例输出 1

1
2
-1

样例输入 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

样例输出 2

3
6
6
7
7
3
1
2
2

样例输入 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

样例输出 3

7
5
5
5
4
2
0
2
1
4
5

样例输入 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

样例输出 4

1
3
1
7
0
4
5
7
8
10
6