13050번 - Maximal Sum 다국어

문제

Marty wants to get back to the future from the past. But the computer system of his time machine is broken, so he needs to make some calculations by himself and then enter the results.

Marty has two arrays of integers: a[1..n] and b[1..m]. For each b_j Marty needs to find the segment a[l..r] such that each element in it is greater or equal to b_j and the sum of elements a[l] + a[l + 1] + ... + a[r] is maximal possible. These sums must be entered into time machine's computer system to get Marty back to the future.

Help him, write the program to solve this problem.

입력

The first line of input contains two integers n and m (1 ≤ n, m ≤ 10⁵) — the sizes of arrays a and b, respectively.

The second line contains n integers a_i ( -10⁹ ≤ a_i ≤ 10⁹).

The third line contains n integers b_j ( -10⁹ ≤ b_j ≤ 10⁹).

출력

Output m integers, the j-th of them must be the required maximal sum for b_j. If there is no such segment in a array, output 0 instead.

제한

힌트