Gats and the Temperamental String
Gats found a long string with knots, numbered from to from left to right. Each knot changes the amount of loose string, called slack.
For knot , the slack changes by when Gats touches it. The value may be negative.
Gats is asked independent questions. In question , he starts immediately before knot with exactly slack. He then tries to touch knots in order.
When Gats tries to touch a knot, its slack change is applied immediately. If the slack would become negative, Gats does not touch that knot and stops. Otherwise, the knot is touched, and Gats may continue to the next knot.
For each question, determine the index of the last knot Gats can touch.
Input
The first line contains two integers and (), the number of knots and the number of questions.
Output
For each question, print one line containing a single integer .
The value must be the index of the last knot Gats can touch for the -th question. If Gats cannot touch knot , print . If Gats can touch every knot from through , print .
Samples
Sample 1
Input
5 4 3 -5 4 -2 -3 1 1 1 2 3 0 4 1
Output
1 4 4 3
In the first question, Gats can touch knot , but touching knot would make the slack negative. In the second question, slack value is allowed, so the first impossible knot is knot .
Sample 2
Input
3 3 -2 5 -1 1 1 1 2 2 0
Output
0 3 3
In the first question, knot would immediately make the slack negative, so the printed value is . In the second question, the slack becomes exactly after knot , which is still allowed.