该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

终于放假了的徐老师又双叕来到了一个新的城市旅游！

这一次他来到的城市是一座以 窗外风景 为看点的城市，也就是说在这个城市旅游，重点在于路上的风景，而不是具体的某个景点

这个城市一共有 $n$ 个街区，街区之间由 $n-1$ 条道路连接，每条道路的风景美丽程度可以形式化的用一个数字来表示

也就是说第 $i$ 条道路会连接编号为 $u_i,v_i$ 的两个街区，并且这条道路的风景美丽程度为 $a_i$

但是这个城市的景点之间相似度比较高，所以会导致在旅游时，去过的景点越多，反而会因为审美疲劳而觉得景点没那么有意思，而徐老师通过一些道路从一个街区 $x$ 到达街区 $y$ 时，他这次旅行最终获得的快乐度将会是经过的每条道路的风景美丽程度的最大公约数

也就是说如果徐老师如果连续通过三条道路 $i,j,k$，那么他最终会获得的快乐度将是 $gcd(a_i,a_j,a_k)$

现在徐老师正在做旅行规划，但是他又是一个很纠结的人，他这次旅游想要经过正好 $m$ 条道路，但是又怕经过的道路太多导致快乐度下降

所以他决定问问你，当徐老师决定正好经过 $m$ 条道路（不允许重复经过同一条道路）的情况下，如何规划路径可以使得他获得的快乐度是最高的？

输入格式

输入第一行包含一个整数 $n$，表示街区数量

接下来 $n-1$ 行，每行三个整数 $u_i,v_i,a_i$ 表示一条道路信息

接下来一行输入一个整数 $T$，表示 $T$ 次询问

接下来 $T$ 行，每行一个整数 $m$，表示徐老师想询问正好经过 $m$ 条道路的情况下，他能获得的最高快乐度是多少

输出格式

对于每次询问输出一个整数，表示答案，如果路径不存在，则输出 $-1$

数据范围

对于 $10\%$ 的数据满足：$a_i = 1$

对于另外 $20\%$ 的数据满足：$1 \leq n \leq 1000$

对于另外 $30\%$ 的数据满足：$1 \leq a_i \leq 100$

对于 $100\%$ 的数据满足：$1 \leq n \leq 400000$,$1 \leq T \leq min(100000, n), 1 \leq u_i$,$v_i,m \leq n, 1 \leq a_i \leq 1000000$，保证题目数据随机生成

样例输入

5
1 2 2
1 3 4
2 4 6
2 5 8
3
4
1
3

样例输出

-1
8
2

样例解释

不存在能够经过 $4$ 条道路的方案，所以答案为 $-1$ 当经过 $1$ 条道路时，选择 $4-5$ 这条道路，答案就是 $8$ 当经过 $3$ 条道路时，由于必须经过 $1-2$ 这条道路，所以答案只能是 $gcd(2,?,?)$ 必然为 $2$