Maximal Sum

Marty wants to get back to the future from the past. The computer in his time machine is broken, so he has to work out the numbers himself and type them in.

Marty has two integer arrays: $a[1..n]$ of length $n$ and $b[1..m]$ of length $m$. For each $b_j$ he needs the largest possible sum $a_l + a_{l+1} + \cdots + a_r$ over the segments $a[l..r]$ whose elements are all greater than or equal to $b_j$.

A segment is never empty, so $l \le r$ holds and the largest sum can be negative. If no element of $a$ is greater than or equal to $b_j$, no segment satisfies the condition.

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 10^5$), the sizes of the arrays $a$ and $b$.

The second line contains $n$ integers $a_i$ ($-10^9 \le a_i \le 10^9$).

The third line contains $m$ integers $b_j$ ($-10^9 \le b_j \le 10^9$).

Print $m$ integers on one line, separated by single spaces. The $j$-th number is the largest segment sum for $b_j$, or $0$ if no segment satisfies the condition.