Con đường tơ lụa, là một hệ thống các con đường buôn bán nổi tiếng đã từ hàng nghìn năm nối châu Á với châu Âu. Tuyến giao thương này còn xuất hiện trong một tác phẩm nổi tiếng của Trung Quốc - Tây Du Ký. Các vương quốc và con đường trên tuyến giao thương này tạo thành một mạng lưới rộng lớn gồm $N$ vương quốc. Trong bài toán này, các vương quốc được đánh số từ $1$ đến $N$. Một con đường sẽ kết nối hai vương quốc khác nhau, cho phép di chuyển buôn bán giữa hai vương quốc. Các vương quốc được kết nối với nhau bằng các con đường một cách tối ưu sao cho từ một vương quốc có đúng một đường đi đến mỗi vương quốc còn lại.

Tương truyền rằng, có một loại gia vị đặc biệt mà mọi vương quốc trên tuyến giao thương đều muốn có. Giá trị mua và bán loại gia vị này tại mỗi vương quốc là khác nhau. Tại vương quốc $i$, người ta có thể mua một túi hoặc bán một túi gia vị này với giá $P_i$ đơn vị vàng. Meng Ting là một buôn lái khét tiếng trên tuyến đường này và quyết tâm tận dụng sự chênh lệch giá giữa các vương quốc để làm giàu. Chiến thuật của Meng Ting đó là xuất phát từ vương quốc $S$, Meng Ting sẽ xác định vương quốc nơi kết thúc chuyến đi, gọi là $T$. Trên đường đi từ $S$ đến $T$, Meng Ting sẽ có 3 lựa chọn:

1. Di chuyển tiếp đến vương quốc khác mà không buôn bán.
2. Nếu túi trống, Meng Ting có thể mua thật nhiều gia vị đặc biệt tại vương quốc này để lấp đầy túi hàng với giá $P_i$ đơn vị vàng.
3. Nếu túi đầy, Meng Ting có thể bán gia vị trong túi cho vương quốc hiện tại đến khi hết và nhận được $P_i$ đơn vị vàng.

Lưu ý rằng, tại mỗi vương quốc Meng Ting sẽ mua đến khi đầy túi hoặc bán đến khi hết, do đó Meng Ting sẽ không mua dồn gia vị tại nhiều nơi hoặc bán từng phần.

Có $Q$ vương quốc tiềm năng Meng Ting muốn chọn làm nơi xuất phát, tại mỗi điểm xuất phát, bạn hãy giúp Meng Ting xác định lượng vàng lớn nhất Meng Ting thu về được từ chuyến đi. Biết rằng, Meng Ting đem theo rất nhiều tiền và sẵn sàng mua với bất kì giá nào.

Input

• Dòng đầu tiên chứa hai số nguyên $N, Q$ ~(1 \le N, Q \le 10^5)~ - lần lượt là số vương quốc và số điểm xuất phát cần khảo sát;
• Dòng thứ hai chứa $N$ số nguyên dương ~P_1, P_2, \dots, P_N~ ~(1 \le P_i \le 10^9)~ - cho biết giá một túi gia vị đặc biệt tại mỗi vương quốc;
• $N-1$ dòng tiếp theo, mỗi dòng gồm 2 số nguyên $u, v$ ~(1 \le u, v \le N, u \neq v)~ - cho biết có một con đường nối giữa hai vương quốc $u$ và $v$;
• Dòng cuối cùng chứa $Q$ số nguyên phân biệt, cho biết danh sách các vương quốc xuất phát mà Meng Ting muốn khảo sát.

Output

• Với mỗi điểm xuất phát theo thứ tự từ trái sang phải trên input, in ra trên một dòng một số nguyên cho biết số vàng lớn nhất Meng Ting có thể thu về được.

Scoring

• Subtask 1 (20%):
  • Con đường thứ $i$ nối vương quốc $i$ với vương quốc $i+1$,
  • Vương quốc được đánh số lớn có giá gia vị đặc biệt không nhỏ hơn vương quốc được đánh số nhỏ ~P_1 \le P_2 \le \dots \le P_N~;
• Subtask 2 (20%): Con đường thứ $i$ nối vương quốc $i$ với vương quốc $i+1$, $N, Q \le 5000$;
• Subtask 3 (20%): $N, Q \le 5000$;
• Subtask 4 (20%): Con đường thứ $i$ nối vương quốc $i$ với vương quốc $i+1$, $N, Q \le 10^5$;
• Subtask 5 (20%): Không có ràng buộc gì thêm.

Sample 1

Input

5 1
3 6 6 9 10
1 2
2 3
3 4
4 5
1

Output

7

Note

Đây là ví dụ cho subtask 1, 2, và 4, các vương quốc được nối lần lượt $1 - 2 - 3 - 4 - 5$.

Chiến thuật tối ưu khi xuất phát từ $1$ sẽ là chọn vương quốc $5$ làm địa điểm kết thúc.

1. Mua tại vương quốc $1$ với giá $P_1 = 3$.
2. "Bỏ qua" vương quốc $2, 3$ và $4$.
3. Bán tại vương quốc $5$ với giá $P_5 = 10$.

Lợi nhuận của chuyến đi sẽ là $-3 + 10 = 7$.

Sample 2

Input

10 5
5 6 10 9 5 8 8 3 2 3
1 7
8 6
4 8
8 3
5 6
6 10
6 2
9 4
7 3
3 10 2 6 5

Output

6
12
9
7
10

Note

Tại phương án đầu tiên, xuất phát từ vương quốc $6$, Meng Ting có thể chọn vương quốc $3$, khi đó tuyến đường sẽ là ~10\to 6 \to 8 \to 3~.

Thứ tự mua bán như sau:

1. Mua tại vương quốc $10$ với giá $P_{10} = 3$.
2. Bán tại vương quốc $6$ với giá $P_6 = 8$.
3. Mua tại vương quốc $8$ với giá $P_8 = 3$.
4. Bán tại vương quốc $3$ với giá $P_3 = 10$.

Lợi nhuận sau cùng là $-3 + 8 - 3 + 10 = 12$ đơn vị vàng.