Scuza - leo cầu thang (Scuza)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Scuza đứng trước một cầu thang gồm $n$ bậc, đánh số từ $1$ đến $n$. Bậc thứ $i$ có độ cao $a_i$.

Với mỗi truy vấn, Scuza có khả năng bước qua một bậc nếu độ cao của bậc đó không vượt quá giá trị $k$ của truy vấn. Scuza bắt đầu từ bậc đầu tiên và chỉ có thể tiếp tục đi lên khi mọi bậc trước đó đều vượt qua được.

Với mỗi $k$, hãy tính tổng độ cao của tất cả các bậc trong tiền tố dài nhất mà Scuza có thể leo qua.

Phiên bản nguồn có nhiều test case. Trong Phước Hưng OJ, mỗi file .in chứa đúng một test case.

Input

• Dòng đầu chứa hai số nguyên $n,q$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\ldots,a_n$, là độ cao các bậc.
• Dòng thứ ba chứa $q$ số nguyên $k_1,k_2,\ldots,k_q$, mỗi số tương ứng với một truy vấn.

Output

In $q$ số nguyên trên một dòng. Số thứ $i$ là tổng độ cao các bậc Scuza có thể leo qua với giá trị $k_i$.

Subtask

Điều kiện chung đã đối chiếu với nguồn:

• $1\le n,q\le2\cdot10^5$

• $1\le a_i\le10^9$

• $0\le k_i\le10^9$

• Nguồn gốc có nhiều test; bản Phước Hưng OJ dùng đúng một test trong mỗi file .in.

• Subtask 1 — 20%: $n,q\le40$

• Subtask 2 — 30%: $a_1\le a_2\le\cdots\le a_n$.

• Subtask 3 — 50%: không có điều kiện bổ sung ngoài các điều kiện chung ở trên.

Ví dụ

Input

5 4
1 2 1 4 3
0 1 2 4

Output

0 1 4 11

Giải thích

Cầu thang có độ cao

• Với $k=0$, bậc đầu tiên có độ cao $1>0$, nên tổng bằng $0$.
• Với $k=1$, Scuza qua được bậc đầu tiên nhưng dừng ở bậc thứ $2$ vì $2>1$, nên tổng bằng $1$.
• Với $k=2$, ba bậc đầu đều không vượt quá $2$, còn bậc thứ $4$ có độ cao $4$, nên tổng là $1+2+1=4$.
• Với $k=4$, mọi bậc đều có độ cao không quá $4$, nên tổng là $1+2+1+4+3=11$.