857. 宝石迷阵

小明参加了一个夺宝游戏,游戏的规则是这样的,有一个树形迷宫,树上的每个节点$t_i$都包含价值为$a_i$的宝物,树上的每条边都有一个标记$l_i$。

在树上,只能从父亲节点向儿子节点开始走,1号节点为树的根节点。

在游戏开始时,小明的初始位置会被指定为树的某个节点,小明需要给出一个长度为k的标记序列(k不小于0),从开始节点沿着这个序列进行运动,直到对应的位置,拿到该位置对应的宝物。

但是,小明发现了这个游戏存在一些漏洞,因为每条边的标记可能相同。

因此,指定的标记序列可能有多个终点,而主办方会把每个符合条件的终点的宝物均取出来作为小明的奖品。

现在小明想知道在哪个点出发,获得宝物的价值最高,因此他有Q个问题,需要聪明的你帮他解答一下。

输入格式

第一行包含两个整数N和Q。

第二行包含N个整数$a_i$,表示每个节点的宝物的价值。

接下来N-1行,每行包含两个整数u,v和一个小写字母q,表示u和v之间存在一个标记为q的边。

接下来Q行,每行包含一个整数$t_i$,表示询问从$t_i$点出发,能获取的最大的宝物的价值是多少。

输出格式

输出共Q行,每行包含一个询问中,能获取的最大宝物的价值。

数据范围

$1 \le N,Q \le 20000$,
$0 \le a_i \le 1000$,
$1 \le u,v \le N$,
$’a’ \le q \le ‘z’$

树的结构是随机生成的。

输入样例:

5 5
1 2 3 4 5
1 2 a
1 3 a
3 4 b
3 5 b
1
2
3
4
5

输出样例:

9
2
9
4
5