Cho hai số nguyên dương ~N~ và ~Q~.

Có một cây gồm ~N~ đỉnh, mỗi đỉnh thứ ~i~ ~(1\leq i\leq N)~ cây có một giá trị ~A_i~. Bạn cần trả lời ~Q~ truy vấn có dạng như sau:

• Cho một đỉnh ~X~ ~(1\leq X\leq N)~, hãy tìm đỉnh ~Y~ sao cho giá trị

$$A_Y - A_X - D(X,\ Y)^2$$

là lớn nhất, với ~D(X,\ Y)~ là số cạnh trên đường đi ngắn nhất từ đỉnh ~X~ đến đỉnh ~Y~ trên cây, sau đó đưa ra giá trị lớn nhất đó.

Dữ liệu - Nhập từ tệp văn bản TREE.inp:

• Dòng đầu tiên gồm hai số nguyên dương ~N~ và ~Q~ ~(1\leq N,\ Q\leq 2\times 10^5)~.
• Dòng tiếp theo gồm ~N~ số nguyên ~A_1,\ A_2,\ \dots,\ A_N~ ~(1\leq A_1,\ A_2,\ \dots,\ A_N\leq 10^9)~.
• ~N - 1~ dòng tiếp theo mỗi dòng gồm hai số nguyên ~U~ và ~V~ mô tả có một cạnh từ đỉnh ~U~ đến đỉnh ~V~ trên cây.
• ~Q~ dòng tiếp theo mỗi dòng gồm một số nguyên ~X~ mô tả các truy vấn ~(1\leq X\leq N)~.

Kết quả - Ghi ra tệp văn bản TREE.out:

• Gồm ~Q~ dòng chứa kết quả bài toán.

Chấm điểm

Ví dụ

Dữ liệu (TREE.inp)

6 6
10 5 15 6 12 5
1 2
1 3
2 4
2 5
3 6
1
2
3
4
5
6

Kết quả (TREE.out)

4
6
0
2
0
9

Giải thích

• Với đỉnh ~X = 1~, ta tìm được đỉnh tương ứng là ~Y = 3~, khi đó, giá trị cần tìm là ~A_3 - A_1 - D(1,\ 3)^2 = 15 - 10 - 1 = 4~.
• Với đỉnh ~X = 2~, ta tìm được đỉnh tương ứng là ~Y = 3~, khi đó, giá trị cần tìm là ~A_3 - A_2 - D(2,\ 3)^2 = 15 - 5 - 4 = 6~.
• Với đỉnh ~X = 3~, ta tìm được đỉnh tương ứng là ~Y = 3~, khi đó, giá trị cần tìm là ~A_3 - A_3 - D(3,\ 3)^2 = 15 - 15 - 0 = 0~.
• Với đỉnh ~X = 4~, ta tìm được đỉnh tương ứng là ~Y = 5~, khi đó, giá trị cần tìm là ~A_5 - A_4 - D(4,\ 5)^2 = 12 - 6 - 4 = 2~.
• Với đỉnh ~X = 5~, ta tìm được đỉnh tương ứng là ~Y = 5~, khi đó, giá trị cần tìm là ~A_5 - A_5 - D(5,\ 5)^2 = 12 - 12 - 0 = 0~.
• Với đỉnh ~X = 6~, ta tìm được đỉnh tương ứng là ~Y = 3~, khi đó, giá trị cần tìm là ~A_3 - A_6 - D(6,\ 3)^2 = 15 - 5 - 1 = 9~.
• Dưới đây là hình dạng của cây: