ami có một cái cây, mỗi nút có 1 giá trị. Độ dài của một đường đi từ \(u\) đến \(v\) là tổng các nút trên đường đi từ \(u\) đến \(v\). Tìm đường đi có độ dài lớn nhất.

Input

• Dòng đầu tiên chứa \(t\) là số câu hỏi.
• Mỗi câu hỏi có dạng sau:
  • Dòng đầu tiên chứa 1 số nguyên \(N\) là số đỉnh của cây.
  • Dòng tiếp theo chứa \(n\) số nguyên \(a_i\) là giá trị nút \(i\).
  • \(N-1\) dòng tiếp theo, mỗi dòng chứa 2 số \(u\) và \(v\) là một cạnh của cây.

Output

• \(N\) số, số \(i\) là đường đi lớn nhất từ đỉnh \(i\) đến một đỉnh còn lại.

Example

1
3
1 2 3
1 2
3 2

6 5 6

Giới hạn

• \(\sum n \leq 5 \cdot 10^6\)
• \(1 \leq a_i \leq 10^9\)
• \(1 \leq u, v \leq N, u \neq v\)