魔王的真实身份是去年 Hobanwoo 养的宠物树。
这棵树依然处于混乱状态，不断地变换着根节点。Hobanwoo 想要通过树的根节点注入圣水来净化这棵树。
这棵树由 $N$ 个节点和 $N-1$ 条边组成，所有节点从 $1$ 到 $N$ 编号，且每个节点都有一个可以存储圣水的空间。
当圣水流入某个节点 $V$ 时，遵循以下规则：
- 圣水只能流向与 $V$ 相连的子节点。
- 如果没有子节点，或者所有子节点内部都已注满圣水，则 $V$ 内部的空间开始注满圣水。
- 如果节点内部的空间大小为 $t$，则注满该空间需要 $t$ 单位的圣水。
- 总是同时向与 $V$ 相连且尚未注满圣水的子节点中，编号最大和编号最小的节点注入等量的圣水。
当节点 $M$ 的空间被圣水注满时，树即被净化。
请帮助因树的根节点不断变化而感到困惑的 Hobanwoo，完成树的净化。
输入格式
第一行包含两个空格分隔的整数 $N$ 和 $M$，分别表示树的节点数和需要注满圣水的节点编号。 第二行包含 $N$ 个空格分隔的整数 $a_1, a_2, a_3, \dots, a_n$，其中 $a_i$ 表示节点 $i$ 内部可以存储圣水的空间大小。 接下来的 $N-1$ 行，每行给出树的一条边信息。 ($1 \le M \le N \le 300,000$) ($1 \le a_i \le 10^9$)
输出格式
输出 $N$ 行。 第 $i$ 行输出当节点 $i$ 为根时，为了净化树，需要向根节点注入的圣水的最小值。
样例
输入 1
1 1 123456789
输出 1
123456789