时间限制： 5.0 秒 空间限制： 1024 MiB

题目背景

よくまあここまで来た歴史を振り返ると

気が遠くなりそうになる だけど

荷物と遺伝子を乗せ一緒に揺られながら

行こうぜ この命は一瞬もいいところ

--- Asian Soul by Jun Maeda & MANYO & Yanaginagi

题目描述

给定一颗节点编号为 \(1, 2, \ldots, n\) 的树，其中根节点的编号为 \(1\)。

给定一个只包含 \(1\) 至 \(n\) 中整数的长度为 \(m\) 的数列 \(a_1, a_2, \ldots, a_m\)，每个元素象征着树上对应编号的结点。

你要回答 \(q\) 次询问。每次询问给定数列上的一个区间和树上的一个结点，查询在区间内选点和树上给定点求 LCA 后，所得到结点编号的最大值。

具体地，我们假设树上结点 \(u, v\) 的 LCA 为 \(LCA(u, v)\)，则一组询问 \(l, r, u\) 需要你求出 \(\max_{l \le k \le r} LCA(a_k, u)\)。

输入格式

从标准输入读入数据。

第一行三个整数 \(n, m, q\)（\(1 \le n, m, q \le 5 \times 10^5\)）。

接下来 \(n - 1\) 行，每行两个数 \(u, v\)，代表树上一条连接 \(u, v\) 的边。

接下来一行 \(m\) 个数，表示给定的数列 \(a_1, a_2, \ldots, a_m\)（\(1 \le a_i \le n\)）。

接下来 \(q\) 行，每行三个数 \(l, r, u\)（\(1 \le l \le r \le m, 1 \le u \le n\)），表示关于数列上区间 \(a_l \ldots a_r\) 和树上结点 \(u\) 的一组询问。

输出格式

输出到标准输出。

对于每组询问依次输出一行一个数，表示对应询问的答案。

样例

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

样例 1 输出

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

样例 1 解释

树的形态如图所示。

样例 2

见题目目录下的 2.in 与 2.ans。

样例 3

见题目目录下的 3.in 与 3.ans。

样例 4

见题目目录下的 4.in 与 4.ans。

样例 5

见题目目录下的 5.in 与 5.ans。

样例 6

见题目目录下的 6.in 与 6.ans。

样例 7

见题目目录下的 7.in 与 7.ans。

样例 8

见题目目录下的 8.in 与 8.ans。

样例 9

见题目目录下的 9.in 与 9.ans。

样例 10

见题目目录下的 10.in 与 10.ans。

提示

本题提供了若干可供下载的样例，方便你的调试，请勿作大量无意义提交。