An có ~N~ chiếc kẹo dự định chia cho ~M~ bạn được đánh số từ 1 đến ~M~. Bạn nào cũng sẽ nhận được tối thiểu 1 chiếc kẹo. An biết rằng, bạn thứ ~i~ ~(1 \le i \le M)~ có mức độ thích đồ ngọt là ~D_i~. Gọi ~S_i~ là số lượng bạn nhận được nhiều kẹo hơn bạn thứ ~i~. Khi đó, độ vui vẻ của bạn thứ ~i~ sẽ bị giảm đi ~D_i \times S_i~.

Yêu cầu: Cho ~T~ truy vấn ~N_1, N_2, \dots, N_T~ tương ứng với số kẹo mà An có. Với mỗi truy vấn, hãy giúp An tìm cách chia kẹo để tổng độ vui vẻ bị giảm đi của ~M~ bạn là nhỏ nhất.

Input

• Dòng đầu tiên gồm hai số nguyên ~M, T~ ~(1 \le M \le 100; 1 \le T \le 10^5)~ là số lượng bạn của An và số truy vấn;
• Dòng thứ hai gồm ~M~ số nguyên ~D_1, D_2, \dots, D_M~ ~(0 \le D_i \le 10^5; 1 \le i \le M)~ là mức độ thích đồ ngọt của ~M~ bạn;
• Dòng thứ ba gồm ~T~ số nguyên mô tả các truy vấn tương ứng là số kẹo mà An có: ~N_1, N_2, \dots, N_T~ ~(1 \le i \le T; M \le N_i \le 10^9)~.

Output

Gồm một dòng chứa ~T~ số, số thứ ~i~ ~(1 \le i \le T)~ là tổng độ vui vẻ bị giảm đi nhỏ nhất trong trường hợp An có ~N_i~ chiếc kẹo.

Scoring

Sample Input 1

3 2
100 200 300
5 6

Sample Output 1

200 0

Notes

• Truy vấn 1: có thể chia số kẹo như sau: 1, 2, 2.
• Truy vấn 2: có thể chia đều số kẹo cho mỗi bạn là 2, 2, 2.