Given a tree with $n$ nodes labeled $1, 2, \dots, n$, where the root is node $1$. Given a sequence $a_1, a_2, \dots, a_m$ of length $m$ containing integers from $1$ to $n$, where each element represents the node in the tree with the corresponding label.

You need to answer $q$ queries. Each query provides a range of the sequence and a node in the tree. You need to find the maximum node label among the Lowest Common Ancestors (LCA) of the nodes in the given range and the specified node. Specifically, if we denote the LCA of tree nodes $u$ and $v$ as $\text{LCA}(u, v)$, for a query $(l, r, u)$, you need to find $\max_{l \le k \le r} \text{LCA}(a_k, u)$.

Input

Read from standard input. The first line contains three integers $n, m, q$ ($1 \le n, m, q \le 5 \times 10^5$). The next $n-1$ lines each contain two integers $u, v$, representing an edge between nodes $u$ and $v$ in the tree. The next line contains $m$ integers $a_1, a_2, \dots, a_m$ ($1 \le a_i \le n$). The next $q$ lines each contain three integers $l, r, u$ ($1 \le l \le r \le m, 1 \le u \le n$), representing a query for the sequence range $a_{l \dots r}$ and tree node $u$.

Output

Output to standard output. For each query, output the answer on a new line.

Examples

Input 1

10 12 20
1 10
1 9
9 4
9 5
4 8
4 7
5 2
7 6
2 3
10 8 6 4 3 2 5 7 1 4 6 7
5 8 1
1 12 1
5 6 2
1 3 2
5 5 3
5 7 3
8 12 4
1 5 4
1 1 5
5 6 5
11 12 6
1 2 6
9 12 7
7 9 7
1 4 8
6 11 8
1 1 9
9 10 9
2 12 10
1 1 10

Output 1

1
2
9
3
5
4
9
1
5
7
4
7
9
8
9
1
9
1
10

Note

The structure of the tree is as shown in the figure.