Задания прошлых чемпионатов

"E" Максимальная сумма / Разогревочный раунд RCC 2016
Ограничение по времени 2 секунды
Ограничение по памяти 256 мегабайт

Марти хочет вернуться из прошлого в свое время. Но бортовой компьютер машины времени сломался, поэтому Марти придется выполнить некоторые вычисления вручную, а затем вбить данные, полученные в результате этих вычислений, в бортовой компьютер.

А именно: у Марти есть массив целых чисел a[1..n] и массив целых чисел b[1..m], которые Док считал из оперативной памяти компьютера. От Марти требуется для каждого числа bj найти в массиве a непустой отрезок a[l..r], каждый элемент которого не меньше bj, и среди всех таких — отрезок с максимальной суммой элементов a[l] + a[l + 1] + ... + a[r]. Суммы на этих отрезках нужно вбить в компьютер, для того чтобы машина времени доставила Марти в обратно.

Напишите программу, которая решит данную задачу.

Формат входных данных

В первой строке находятся два натуральных числа n, m (1 ≤ n, m ≤ 105) — длина массива ai и массива bj, соответственно.

В следующей строке содержатся n целых чисел ai ( - 109 ≤ ai ≤ 109).

В следующей строке содержатся m целых чисел bj ( - 109 ≤ bj ≤ 109).

Формат выходных данных

В единственной строке выведите m целых чисел: j-е из которых равно сумме для числа bj. Если отрезка, удовлетворяющего условиям, не нашлось, выведите 0.

Примеры
Входные данные
5 5
-1 2 3 4 -5
-5 4 10 2 -1
Выходные данные
9 4 0 9 9
Входные данные
5 5
3 -2 3 -5 -3
-1 -2 -3 -4 -5
Выходные данные
3 4 4 4 4
 

Вход

ВКонтакте Facebook

Забыли пароль?

Регистрация

На вашу электронную почту была
отправлена инструкция по восстановлению пароля.