마왕의 정체는 작년에 호반우가 키우던 애완용 트리였다.
트리는 여전히 어지러운 채로 루트를 바꾸고 있으며 호반우는 트리의 루트를 통해서 신성한 물을 흘려보내 트리를 정화하려고 한다.
트리는 N개의 노드와 N-1개의 간선으로 이루어져 있으며 모든 노드는 1번부터 N번까지의 번호와 신성한 물을 저장할 수 있는 공간을 가진다.
어떤 노드 V에 신성한 물이 흘러 들어올 때 아래의 규칙에 따른다.
V와 연결된 자식 노드로만 신성한 물을 흘려보낼 수 있다.- 자식 노드가 없거나 모든 자식 노드 내부가 신성한 물로 가득 찼다면
V내부의 공간이 신성한 물로 차기 시작한다. - 노드 내부의 크기가
t라면 내부를 가득 채우는데t만큼의 신성한 물이 필요하다. - 항상
V와 연결된 신성한 물로 가득 차지 않은 자식 노드 중 번호가 가장 큰 노드와 가장 작은 노드에 동일한 양의 신성한 물을 동시에 흘려보낸다.
트리는 M번 노드의 공간이 신성한 물로 가득 차면 정화된다고 한다.
트리의 루트가 계속 변해 어지러워하는 호반우를 도와 트리를 정화해 보자.
Input
첫 번째 줄에 트리의 노드 개수 N과 신성한 물로 가득 차야 할 노드 번호 M이 공백을 두고 주어진다.
두 번째 줄에 a1, a2, a3 ... an까지 N개의 수가 공백을 두고 주어진다.
ai는 i번 노드가 내부에 신성한 물을 저장할 수 있는 공간의 크기이다.
세 번째 줄부터 N-1개의 줄에 걸쳐 트리의 간선 정보가 주어진다.
(1 ≤ M ≤ N ≤ 300,000)
(1 ≤ ai ≤ 10^9)
Output
N개의 줄에 걸쳐 답을 출력한다.
i번째 줄에는 i번 노드가 루트일 때 트리가 정화되기 위해 루트로 흘려보낼 신성한 물의 최솟값을 출력한다.
Examples
Input 1
1 1 123456789
Output 1
123456789