이건 버그야!

상민이와 지수가 전쟁 시뮬레이션 게임을 한다. 게임에는 $N$개의 지역이 있으며, 각 지역은 전투력을 가지고 있다. 지역들은 $N-1$개의 길로 연결되어 있으며, 연결된 지역 사이를 이동할 수 있다. 모든 지역은 방향이 없는 트리 구조를 이루므로, 임의의 지역에서 다른 지역으로 언제나 이동할 수 있다.

게임 한 판은 다음과 같이 진행된다.

1. 상민이가 지역 하나를 골라 요새를 설치한다.
2. 지수가 요새가 설치되지 않은 지역을 골라 자신의 선봉으로 지정한다. 선봉의 전방은 상민이의 요새를 향하는 방향이다.
3. 지수 선봉의 후방 지역들은 모두 지수의 세력에 편입되어, 선봉과 함께 상민이의 요새를 공격한다.
4. 상민이의 요새는 지수의 공격을 막는다. 요새의 전방은 지수의 공격이 들어오는 방향이다.
5. 상민이 요새의 후방 지역들은 모두 상민이의 세력에 편입되어, 지수의 공격을 막는다.
6. 지수 세력의 전투력이 상민이 세력의 전투력보다 크면 지수가 승리하고, 그렇지 않으면 패배한다.

각 세력의 전투력은 다음과 같이 계산된다.

$\sum_{u\in\text{세력}} A_u \times (\max_{v\in\text{세력}}(dist(P, v)) - dist(P, u) + 1)$

여기서 $P$는 플레이어가 각 세력의 요새 혹은 선봉으로 지정한 지역이고, $dist(a, b)$는 지역 $a$와 지역 $b$ 사이의 거리이다.

예를 들어, <그림 1>에서 지수의 세력은 $\{(2) \times 1\} + \{(3) \times 2\} + \{(8 + 6 + 1) \times 3\} + \{(2 + 7) \times 4\} + \{(4) \times 5\} + \{(5) \times 6\} = 139$의 전투력을 갖는다.

<그림 1> 지수의 세력 예시

이 게임의 고인물인 지수는 게임에 버그가 있음을 알고 있다. 게임 내 전투력의 자료형이 unsigned int로 구현되어, 세력의 전투력이 $2^{32}-1$을 넘어가는 순간 오버플로우가 발생해 0부터 다시 시작하게 된다. 이 버그를 잘 이해하고 있는 지수는 버그를 적극 활용해 상민이에게 대승을 거두고자 한다.

첫 줄에는 지역의 개수 $N$, 진행될 게임의 횟수 $Q$가 주어진다.

두 번째 줄부터 $N-1$개의 줄에 걸쳐 지역 간 길의 정보가 주어진다. 각 줄에는 $u$, $v$ ($1 \le u, v \le N$)가 주어지며, 이는 $u$번 지역과 $v$번 지역이 연결되어 있다는 의미이다.

$N+1$번째 줄에는 1번 지역부터 $N$번 지역까지의 전투력 $A_i$ ($1 \le i \le N$)가 차례로 주어진다.

$N+2$번째 줄부터 $Q$개의 줄에 걸쳐 각 판마다 상민이가 요새를 설치한 지역의 번호 $x$ ($1 \le x \le N$)가 주어진다.

$Q$개의 줄에 걸쳐 출력한다. 각 판마다 상민이가 지역 $x$ ($1 \le x \le N$)에 요새를 설치했을 때, 지수가 선봉을 지정하여 얻을 수 있는 "지수의 전투력 - 상민이의 전투력"의 최댓값을 한 줄씩 출력한다.

$1 \le Q \le 100000$

$0 \le A_i < 2^{32}$