在元旦激光炮的轰炸下，圣诞老人终于招架不住仓皇而逃，元旦三侠立刻展开追击行动。

有 $n$ 座城市，之间有 $n-1$ 条道路连接成一个树形结构。每个城市有一个停留时间 $w_i$，只要圣诞老人来到 $i$ 号城市就必须停留 $w_i$ 的时间休息一下。

圣诞老人的逃跑路线可以用长度 $l$ 的序列 $s_1,s_2,\dots ,s_l$ 表示（$l$ 是某个正整数），他会依次飞过 $s_1,s_2,\dots ,s_l$ 号城市然后飞向火星找楼主聊人生，耗费的时间为经过的城市的停留时间之和，即 $\sum _{i=1}^l{w}_{s_i}$。（圣诞老人可能经过同一个城市多次）

由于元旦三侠身手敏捷，圣诞老人在城市 $i$ 的时候下一步能飞到的城市是受限制的。对于每个城市 $i$ 有三个整数参数 $a_i,b_i,c_i$ （$1\le a_i,b_i,c_i\le n$）。从城市 $i$ 出发能飞到城市 $j$ 当且仅当下面三个条件中有至少一个成立：

• 从城市 $a_i$ 出发沿道路行走到城市 $b_i$ 必经过城市 $j$。
• 从城市 $b_i$ 出发沿道路行走到城市 $c_i$ 必经过城市 $j$。
• 从城市 $c_i$ 出发沿道路行走到城市 $a_i$ 必经过城市 $j$。

所以圣诞老人的长度为 $l$ 的逃跑路线 $s$ 必须满足对于所有的 $1\le i<l$ 能从 $s_i$ 出发飞到 $s_{i+1}$。

由于圣诞老人在和元旦三侠玩心理战，他会选择耗费时间前 $k$ 小的逃跑路线之一（长度 $l$ 不限）。请帮助元旦三侠找出耗费时间前 $k$ 小的逃跑路线的耗费时间吧。

由于世界被圣诞老人毁灭得差不多了，元旦三侠手上的电脑只有 $100\mathtt{\text{MB}}$内存。请节约使用内存。测评机是 64 位机，指针类型和 long 类型均为 $8$ 个字节。

消灭圣诞老人！地球属于人类！

输入格式

第一行两个正整数 $n,k$。

第二行 $n$ 个整数，第 $i$ 个整数表示 $w_i$。保证 $1\le w_i\le {10}^8$。

第三行 $n-1$ 个整数，第 $i$ 个整数即 $p_{i+1}$ 表示 $i+1$ 号城市与 $p_{i+1}$ 号城市之间有道路连接。保证 $1\le p_{i+1}<i+1$。

接下来 $n$ 行，第 $i$ 行包含三个整数 $a_i,b_i,c_i$。保证 $1\le a_i,b_i,c_i\le n$。

输出格式

$k$ 行，每行一个整数，第 $i$ 行表示第 $i$ 小的逃跑路线的耗费时间。

样例一

input

4 9
1 10 15 1000
1 2 2
2 2 4
2 2 3
1 3 4
3 3 4

output

1
10
11
15
16
20
21
25
25

样例二

见样例数据下载。这组样例满足 $a_i=b_i$。

样例三

见样例数据下载。

限制与约定

对于所有编号为奇数的测试点，输入中所有 $a_i=b_i$。

保证答案小于等于 ${10}^8$。

时间限制：$3\mathtt{\text{s}}$

空间限制：$100\mathtt{\text{MB}}$

下载

样例数据下载