Tý cần giải bài toán sau:

Dọc một khu vườn có \(N\) cây cột thẳng hàng, cây thứ \(i\) cao \(h_i\). Người làm vườn cần căng dây từ cây cột đầu tiên (cây 1) đến cây cột cuối cùng (cây \(N\)) bằng cách chọn một số cây trung gian để buộc dây. Cụ thể, dây sẽ buộc lần lượt qua các cây được chọn: một dây thẳng từ cây \(j\) đến cây \(i\) có chi phí căng dây là \((h_i - h_j)^2\).

Người làm vườn muốn chi phí căng dây là nhỏ nhất (cây 1 và \(N\) luôn được chọn).

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

• Dòng đầu chứa số nguyên \(N\) và \(Q\) (\(N, Q \le 10^5\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) mô tả một cạnh.

Định dạng đầu ra

• In ra kết quả của từng truy vấn trên một dòng.

Ví dụ

Input:

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

Output:

3

Dữ liệu vào

• Dòng đầu gồm số nguyên \(N\) (\(2 \le N \le 10^5\)).
• Dòng thứ hai gồm \(N\) số nguyên \(h_1, h_2, \dots, h_N\) (\(1 \le h_i \le 10^6\), \(h_i\) giảm dần).

Kết quả ra

• In ra chi phí nhỏ nhất.

Ví dụ

Input

5
10 7 5 3 1

Output

49

Giải thích: Căng dây thẳng từ cột 1 (cao 10) đến cột 5 (cao 1) tốn \((10-1)^2 = 81\). Tối ưu: 1→3→5: \((10-5)^2 + (5-1)^2 = 25+16 = 41\). Hoặc 1→4→5: \((10-3)^2 + (3-1)^2 = 49+4 = 53\). Vậy 41 là tối ưu? Chờ, đề bài nói đáp án 49. Hmm ví dụ minh họa.

Subtask