题目描述

小 A 和小 B 是两名优秀的肯德基三人篮球赛选手。经过一段时间的训练，他们终于迎来了一个假期，于是他们决定在城市里大吃一顿。

这座城市总共有 $n$ 个餐馆，有 $n-1$ 条双向的道路连接着两个餐馆，使得任意两个餐馆都能互相到达。小 A 制定了一个餐馆列表 $a_1,...,a_m$，他决定和小 B 选择一个长度为奇数的区间 $[l,r]$，然后把 $a_l,a_{l+1},...,a_{r-1},a_r$ 这些餐馆吃个遍。他们会选择一个餐馆（不一定要是自己会去的），然后在这个餐馆里住下。在第 $i$ 天，他们会从自己住下的餐馆出发，然后沿着最短路径到达第 $a_{l+i-1}$ 个餐馆就餐，最后回到自己住下的餐馆。

现在，请你帮他们选择出这个住下的餐馆，使得他们经过的路程最短。你需要求出这个餐馆的编号。如果有多个餐馆能达到最小的路程，请输出编号最小的那一个。小 A 和小 B 总共有 $q$ 个假期，他对每个假期都选择了区间，请你帮他对每个假期都求出住下的餐馆。

输入格式

第一行 $n$，表示餐馆的个数；

接下来 $n-1$ 行，每行 $x,y,c$，表示存在一条连接餐馆 $x$ 和 $y$ 的长度为 $c$ 米的双向道路；

第二行 $m$，表示小 A 的列表；

接下来一行 $m$ 个数 $a_1,a_2,...,a_m$，表示列表的内容；

第三行 $q$，表示假期的个数；

接下来 $q$ 行，每行 $l,r$，表示这个区间。

输出格式

输出 $q$ 行，第 $i$ 行表示第 $i$ 个假期的能使得路程和最小的餐馆的最小编号。

样例输入

5
4 3 201
2 4 385
5 3 373
1 3 706
7
5 1 4 1 5 3 5
4
3 5
5 7
2 4
1 3

样例输出

3
5
1
3

子任务

对于所有数据，输入满足 $1\le x\le n, 1\le y\le n, 1\le c\le 10^3$。

对于 $20\%$ 的数据，$n,m,q\le 1000$；

对于 $35\%$ 的数据，$n\le 10^5,m,q\le 2000$；

对于 $60\%$ 的数据，$n\le 10^5,m,q\le 10^5$；

存在另外 $15\%$ 的数据，保证树中每个餐馆最多和两个餐馆直接相连；

对于所有数据，$n\le 3\times 10^5,m\le 5\times 10^5, q\le 10^6$。