You are conducting a study on an ant nest modeled as a tree with $n$ nodes. This ant colony happens to be very technologically advanced and they have $m$ MRT companies. The route for company $i$ is the path between $a_i$ and $b_i$. If you buy a pass for $c_i$ NT dollars, you will be able to travel between any pair of nodes on the path.
As part of your research, you need to find out how much the ants pay for their daily commute. You have to answer $q$ questions, the $j$-th question asks for the minimum amount of money (in NT dollars) you need to travel from $u_j$ to $v_j$ or $-1$ if it's impossible.
The first line contains three integers $n, m, q$ ($2 <= n, m, q <= 10^5$).
Then $n -1$ lines follow, each containing two integers $s, t$ ($1 <= s, t <= n, s != t$) denoting an edge between the $s$-th and $t$-th nodes in the ant nest. It is guaranteed that the given edges form a tree.
Then $m$ lines follow. The $i$-th of them contains three integers $a_i, b_i, c_i$ ($1 <= a_i, b_i <= n, a_i != b_i, 0 <= c_i <= 6$) describing the route for the $i$-th MRT company.
Then $q$ lines follow. The $j$-th of them contains two integers $u_j, v_j$ ($1 <= u_j, v_j <= n$) denoting the $j$-th question.
For each question, output its answer on one line.
## Input
The first line contains three integers $n, m, q$ ($2 <= n, m, q <= 10^5$).Then $n -1$ lines follow, each containing two integers $s, t$ ($1 <= s, t <= n, s != t$) denoting an edge between the $s$-th and $t$-th nodes in the ant nest. It is guaranteed that the given edges form a tree.Then $m$ lines follow. The $i$-th of them contains three integers $a_i, b_i, c_i$ ($1 <= a_i, b_i <= n, a_i != b_i, 0 <= c_i <= 6$) describing the route for the $i$-th MRT company.Then $q$ lines follow. The $j$-th of them contains two integers $u_j, v_j$ ($1 <= u_j, v_j <= n$) denoting the $j$-th question.
## Output
For each question, output its answer on one line.
[samples]
## Scoring
Subtask 1 (9 points): $n <= 1000$ Subtask 2 (20 points): $n, m <= 4000$ Subtask 3 (22 points): For $i = 1, 2, \\dots, m$, node $a_i$ is on the shortest path between node 1 and node $b_i$. Subtask 4 (18 points): For $i = 1, 2, \\dots, m$, $c_i <= 1$ Subtask 5 (27 points): For $i = 1, 2, \\dots, m$, $c_i <= 5$ Subtask 6 (4 points): No additional constraints
**Definitions**
Let $ n \in \mathbb{Z} $ with $ 2 \leq n \leq 3 \times 10^4 $.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of nonzero real numbers, $ a_i \in \mathbb{R} \setminus \{0\} $, all distinct.
**Objective**
Find the index $ j \in \{1, \dots, n\} $ such that the product $ P_j = \prod_{i \neq j} a_i $ is maximized.
Output $ a_j $, the score to be removed.
**Constraints**
- $ a_i \in [-10^6, 0) \cup (0, 10^6] $ for all $ i $
- All $ a_i $ are nonzero and distinct.