Cây khung

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,\dots ,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)$. Như vậy mọi cặp đỉnh $i\ne j$ đều có đúng một cạnh nối (đồ thị đầy đủ); trọng số cạnh có thể âm. Với $n=1$, cây khung không có cạnh nào và có trọng số $0$.

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.

Dữ liệu vào

• 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,\dots ,w_n$ $(|w_i|\le {10}^6)$;
• Dòng thứ ba gồm $q$ số nguyên tương ứng với giá trị $t$ của từng truy vấn, các số có giá trị tuyệt đối không vượt quá ${10}^6$.

Dữ liệu ra

In ra một dòng gồm $q$ số, mỗi số là trọng số của cây khung có trọng số nhỏ nhất tương ứng với từng giá trị $t$, theo thứ tự trong dữ liệu vào, cách nhau bởi dấu cách.

Ràng buộc

• $1\le n\le {10}^5$, $1\le q\le {10}^5$;
• $|w_i|\le {10}^6$;
• $|t|\le {10}^6$ với mọi truy vấn.

Subtasks

• 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$.

Ví dụ