JOI 国有 $N$ 个城市，从 $1$ 到 $N$ 编号，有 $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)$，确定对于公民 $k$，从 $S_k$ 前往 $T_k$ 是否可行，如果可行，计算公民 $k$ 最多可以留下多少金币。

输入格式

第一行三个整数 $N,M,Q$。

接下来 $N-1$ 行，每行两个整数 $A_i$,$B_i$。

接下来 $M$ 行，每行两个整数 $P_j,C_j$。

接下来 $Q$ 行，每行四个整数 $S_k,T_k,X_k,Y_k$。

输出格式

输出 $Q$ 行，第 $k(1\le k\le Q)$ 行表示如果公民 $k$ 可以从 $S_k$ 前往 $T_k$，公民 $k$ 最多可以留下的金币数量，否则输出 $-1$。

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

样例解释

公民 $1$ 可以按如下方式从城市 $3$ 前往城市 $4$。在旅行过后，公民 $1$ 可以留下 $1$ 枚金币。

1. 公民 $1$ 通过路 $2$ 从从城市 $3$ 前往城市 $1$。路 $2$ 上有收费站 $1,2$。公民 $1$ 在收费站 $1$ 处支付 $1$ 枚金币并通过它，在收费站 $2$ 支付 $4$ 枚银币并通过它。在这之后，公民 $1$ 有 $1$ 枚金币和 $7$ 枚银币。
2. 公民 $1$ 通过路 $1$ 从从城市 $1$ 前往城市 $2$。路 $1$ 上没有收费站，通过后公民 $1$ 有 $1$ 枚金币和 $7$ 枚银币。
3. 公民 $1$ 通过路 $3$ 从从城市 $2$ 前往城市 $4$。路 $3$ 上有收费站 $3$。公民 $1$ 在收费站 $3$ 处支付 $5$ 枚银币并通过它。在这之后，公民 $1$ 有 $1$ 枚金币和 $2$ 枚银币。

因为公民 $1$ 不可能在旅行之后保留 $2$ 枚或以上金币，因此第一行输出 $1$。

公民 $2$ 可以按如下方式从城市 $5$ 前往城市 $3$。在旅行过后，公民 $2$ 可以留下 $2$ 枚金币。

1. 公民 $2$ 通过路 $4$ 从从城市 $5$ 前往城市 $2$。路 $4$ 上有收费站 $4$。公民 $2$ 在收费站 $4$ 处支付 $1$ 枚金币并通过它。在这之后，公民 $2$ 有 $3$ 枚金币和 $5$ 枚银币。
2. 公民 $2$ 通过路 $1$ 从从城市 $2$ 前往城市 $1$。路 $1$ 上没有收费站，通过后公民 $2$ 有 $3$ 枚金币和 $5$ 枚银币。
3. 公民 $2$ 通过路 $2$ 从从城市 $1$ 前往城市 $3$。路 $2$ 上有收费站 $1,2$。公民 $2$ 在收费站 $1$ 处支付 $1$ 枚金币并通过它，在收费站 $2$ 支付 $4$ 枚银币并通过它。在这之后，公民 $2$ 有 $2$ 枚金币和 $1$ 枚银币。

因为公民 $2$ 不可能在旅行之后保留 $3$ 枚或以上金币，因此第二行输出 $2$。

因为公民 $3$ 不可能从城市 $2$ 前往城市 $3$，因此第三行输出 $-1$。

这组样例满足子任务 $1,4$ 的限制。

数据范围

对于所有输入数据，满足：

• $2\le N\le {10}^5$
• $1\le M,Q\le {10}^5$
• $1\le A_i,B_i,S_k,T_k\le N,S_k\ne T_k$
• 从任意城市出发，经过一些道路总可以到达任意其他城市
• $1\le P_j\le N-1$
• $1\le C_j\le {10}^9$
• $0\le X_k\le {10}^9,0\le Y_k\le {10}^{18}$

详细子任务及附加限制如下表所示。