Woburn Challenge 2015-16 Round 3 - Senior Division

What is a savior but an emblem of hope – but a monument for the people to look up to? Should he be anything that the world needs him to be – or should he be none of it? What does a savior owe the world? The time has come for the man of steel to finally face these difficult questions. And while Superman is nothing short of a god amongst mortals, Batman is... well, Batman.

Superman knows that fighting the dark knight is going to be no easy task. He knows that Batman will enter the battle with a heavily armored mech-suit with a multitude of unpredictable special abilities. It is very likely that Batman's armor will already be prepped to take on the stupendously powerful blows that Superman can deal. From collaborating with the U.S. government, Superman has received intel saying that Batman's suit has the ability to absorb the kinetic energy from any strike dealt onto it and store it for later use to power Batman's own offensive blows. This is an incredibly sneaky technology, and seems to give Batman a huge edge in battle. However, he has also learned this advanced technology has not yet been perfected. That is, the armor itself may fail at capturing the kinetic energy of the blows, resulting in actual damage being done. Luckily, Superman found out about it beforehand and now has a chance to plan out his attack strategy.

In particular, Superman plans to land ~N~ ~(1 \le N \le 10^6)~ punches onto Batman's armor. The punches are numbered from ~1~ to ~N~, and he will deal them in order. By analyzing the stolen blueprint of the mech-suit, Superman knows that the ~i~-th punch he lands on Batman will deal ~D_i~ ~(-1\,000 \le D_i \le 1\,000)~ units of damage to his suit. Specifically, the damage will be negative if Batman's suit happens to absorb ~|D_i|~ units of Superman's kinetic energy, or it will be positive if the absorption fails and Superman successfully deals ~D_i~ units of damage.

Superman is no fool. In the battle, he will continue to perform punches ~1~ to ~N~ in order, but will stop as soon as the next punch would cause the net damage on Batman's suit to become negative. The government will do its best to help Superman by sabotaging Batman's suit beforehand, so when the battle starts, the amount of initial damage sustained by Batman's suit will be positive. Still, Superman would like to land as many hits onto Batman as possible because it will nonetheless exhaust the aging hero beneath the armor.

Since the only piece of information that Superman doesn't have is the initial damage to Batman's suit when he enters the fight, he would like your help in writing a program that can quickly compute how many punches he'll throw based on the original damage to Batman's suit. In particular, your program must answer ~M~ ~(1 \le M \le 500\,000)~ queries where the ~i~-th query asks: "if Batman's suit were to have ~Q_i~ ~(1 \le Q_i \le 10^9)~ units of damage done to it when he enters the battle, what is the number punches Superman will throw before making the net damage to Batman's suit negative?"

In test cases worth ~6/15~ of the points, ~N \le 1\,000~ and ~M \le 1\,000~.

Input Specification

The first line of input contains two space-separated integers ~N~ and ~M~.
The second line of input contains ~N~ space-separated integers ~D_1, \dots, D_N~.
The third line of input contains ~M~ space-separated integers ~Q_1, \dots, Q_M~.

Output Specification

~M~ lines with a single integer on each line, the answers to queries ~1 \dots M~.

Sample Input

4 3
-3 5 -3 -3
2 3 4

Sample Output

0
3
4

Explanation

If Batman's suit starts with ~2~ units of damage sustained from the sabotage, then punching him would give him energy and immediately lower the damage done to ~-1~, so Superman won't do it.
If the suit starts with ~3~ units of damage, it will be lowered to ~0~ units of damage after receiving the first blow, but raised to ~5~ units of damage after the second blow, and lowered to ~2~ units of damage after the third blow. By then, Superman will have realized that it's not worthwhile to make the fourth blow (which will make the net damage ~-1~).
If the suit starts with ~4~ units of damage, it will have sustained ~3~ units of damage going into the final blow. Thus Superman will be able to deal the last punch and still have a nonnegative damage of ~0~ sustained by the suit. Although this last punch seems to be suboptimal in Superman's favor, he will still deal it nonetheless because he wants the battle to be as long as possible to fatigue Batman.