Tý có một cây gồm \(N\) đỉnh, mỗi đỉnh \(i\) có giá trị \(a_i\). Tý muốn tính tổng giá trị các đỉnh trên đường đi từ \(u\) đến \(v\).

Định dạng đầu vào

• Dòng đầu: hai số nguyên \(N, Q\) (\(1 \le N, Q \le 1000\)).
• Dòng hai: \(N\) số nguyên \(a_i\) (\(1 \le a_i \le 10^6\)).
• \(N-1\) dòng tiếp: mỗi dòng \(u, v\) (\(1 \le u, v \le N\)).
• \(Q\) dòng tiếp: mỗi dòng \(u, v\) là truy vấn.

Định dạng đầu ra

• Với mỗi truy vấn, in ra tổng giá trị trên đường đi.

Ví dụ

Input:

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

Output:

11
14
4

Ràng buộc