A. Asian Soul

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

题目背景

よくまあここまで来た歴史を振り返ると 気が遠くなりそうになる だけど 荷物と遺伝子を乗せ一緒に揺られながら 行こうぜ この命は一瞬もいいところ

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

题目描述

给定一颗节点编号 1, 2, ... , n 的树，其中根节点的编号为 1。 给定一个只包含 1 ~ n 中整数的长度为 m 的数列 a1, a2, ... , am，每个元素象征着 树上对应编号的结点。 你要回答 q 次询问。每次询问给定数列上的一个区间和树上的一个结点，查询在区 间内选点和树上给定点求 LCA 后，所得到结点编号的最大值。 具体地， 我们假设树上结点u, v 的 LCA 为 LCA(u, v)， 则一组询问l, r, u 需要你求 出 maxl≤k≤r LCA(ak, u)。

输入格式

从标准输入读入数据。 第一行三个整数 n, m, q(1 ≤ n, m, q ≤ 5 × 10^5)。 接下来 n - 1 行，每行两个数 u, v，代表树上一条连接 u, v 的边。 接下来一行 m 个数，表示给定的数列 a1, a2, ... , am(1 ≤ ai ≤ n)。 接下来 q 行，每行三个数 l, r, u(1 ≤ l ≤ r ≤ m, 1 ≤ u ≤ n)，表示关于数列上区间 al~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。

提示

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