Vương quốc JOI có \(N\) thành phố, được đánh số từ \(1\) đến \(N\). Thành phố \(1\) là thủ đô. Mỗi thành phố có một giá trị gọi là độ sầm uất; ban đầu, độ sầm uất của thành phố \(i\) là \(C_i\).

Mỗi con đường nối hai thành phố khác nhau và có thể đi theo cả hai chiều. Ban đầu chưa có con đường nào. Bạn dự định xây \(N-1\) con đường. Lần xây dựng thứ \(j\) được thực hiện như sau:

1. Chọn hai thành phố \(A_j\) và \(B_j\) sao cho, chỉ dùng những con đường đã xây, có thể đi từ thành phố \(1\) đến \(A_j\) nhưng không thể đi từ thành phố \(1\) đến \(B_j\).
2. Xây một con đường nối \(A_j\) với \(B_j\). Chi phí là số cặp thành phố \((s,t)\) thỏa mãn đồng thời: cả \(s\) và \(t\) nằm trên đường đi ngắn nhất từ \(1\) đến \(A_j\); khi đi từ \(1\) đến \(A_j\) thì gặp \(s\) trước \(t\); và độ sầm uất hiện tại của \(s\) lớn hơn hẳn độ sầm uất hiện tại của \(t\). Đường đi này là duy nhất và bao gồm cả hai đầu mút \(1\) và \(A_j\).
3. Đổi độ sầm uất của tất cả thành phố trên đường đi từ \(1\) đến \(A_j\) thành độ sầm uất của thành phố \(B_j\).

Hãy tính chi phí của từng lần xây dựng.

Dữ liệu vào

• Dòng đầu chứa số nguyên \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(C_1,C_2,\ldots,C_N\).
• Trong \(N-1\) dòng tiếp theo, dòng thứ \(j\) chứa hai số nguyên \(A_j,B_j\), mô tả lần xây dựng thứ \(j\).

Dữ liệu ra

In \(N-1\) dòng. Dòng thứ \(j\) chứa chi phí của lần xây dựng thứ \(j\).

Ràng buộc

• \(1 \le N \le 100\,000\).
• \(1 \le C_i \le 1\,000\,000\,000\) với \(1 \le i \le N\).
• \(1 \le A_j,B_j \le N\) với \(1 \le j \le N-1\).
• Trước lần xây dựng thứ \(j\), có thể đi từ thành phố \(1\) đến \(A_j\) nhưng không thể đi từ thành phố \(1\) đến \(B_j\) bằng các con đường đã xây.

Phân nhóm

1. \(7\) điểm: \(N \le 500\)
2. \(9\) điểm: \(N \le 4\,000\)
3. \(84\) điểm: Không có ràng buộc bổ sung.

Ví dụ

5
1 2 3 4 5
1 2
2 3
2 4
3 5

0
0
0
2

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

0
0
0
1
1
0
1
2
3

Nguồn

JOI 2018 Spring Training Camp, ngày 1 - Construction of Highway.