The Demon King turned out to be the pet tree that Hobanwoo was raising last year.
The tree is still dizzy and keeps changing its root, and Hobanwoo intends to purify the tree by pouring holy water through the root of the tree.
The tree consists of $N$ nodes and $N-1$ edges, and every node is numbered from 1 to $N$ and has a space that can store holy water.
When holy water flows into a certain node $V$, it follows the rules below:
- Holy water can only flow into the child nodes connected to $V$.
- If there are no child nodes or if the interiors of all child nodes are completely filled with holy water, the space inside $V$ begins to fill with holy water.
- If the size of the space inside a node is $t$, it requires $t$ amount of holy water to fill it completely.
- Holy water is always sent simultaneously in equal amounts to the child node with the largest number and the child node with the smallest number among those connected to $V$ that are not yet completely filled with holy water.
The tree is said to be purified when the space in node $M$ is completely filled with holy water.
Help Hobanwoo, who is distressed because the root of the tree keeps changing, to purify the tree.
Input
The first line contains the number of nodes in the tree $N$ and the node number $M$ that must be filled with holy water, separated by a space. The second line contains $N$ numbers $a_1, a_2, a_3, \dots, a_n$ separated by spaces. $a_i$ is the size of the space inside node $i$ that can store holy water. From the third line, $N-1$ lines follow, providing the edge information of the tree. ($1 \le M \le N \le 300,000$) ($1 \le a_i \le 10^9$)
Output
Output the answer over $N$ lines.
The $i$-th line should output the minimum amount of holy water that must be poured into the root for the tree to be purified when node $i$ is the root.
Examples
Input 1
1 1 123456789
Output 1
123456789