Cây khung 1

Với một đồ thị vô hướng có trọng số và liên thông, ta định nghĩa cây khung của đồ thị là đồ thị con có dạng cây và chứa tất cả các đỉnh của đồ thị. Trọng số của cây khung là tổng trọng số các cạnh thuộc cây. Trong bài toán này, chúng ta sẽ xét cách xây dựng đồ thị và tìm cây
khung có trọng số nhỏ nhất trên đồ thị được tạo ra.

Cho dãy số nguyên \(w_1, w_2, \ldots, w_n\) với số nguyên \(t\), ta xây dựng đồ thị gồm \(n\) đỉnh, đỉnh \(i\) nối với đỉnh \(j\) bằng cạnh vô hướng với trọng số \(w_i \times w_j + t \times (w_i + w_j)\).

Yêu cầu: Có \(q\) truy vấn tương ứng với \(q\) giá trị \(t\), tìm cây khung có trọng số nhỏ nhất tương ứng.

Input

• Dòng đầu chứa hai số nguyên \(n, q\).
• Dòng thứ hai gồm \(n\) số nguyên \(w_1, w_2, \ldots, w_n\ (|w_i| \le 10^6)\).
• Dòng thứ ba gồm \(q\) số tương ứng với từng truy vấn, các số có giá trị tuyệt đối không vượt quá \(10^6\).

Output

• Gồm \(q\) dòng, mỗi dòng là trọng số của cây khung tương ứng với từng giá trị \(t\).

Example

3 2
1 0 -1
0 1

-1 -2 

Scoring

• Có \(40\%\) số test ứng với \(40\%\) số điểm có \(n \le 10^3; q \le 5\).
• Có \(30\%\) số test khác ứng với \(30\%\) số điểm có \(n \le 10^5; q \le 5\).
• Có \(30\%\) số test còn lại ứng với \(30\%\) số điểm có \(n \le 10^5; q \le 10^5\).