Tianjin University Online Judge
Contests Virtual Contests Problems Submit Runs Status Rank List Forum

3478.   Music Notes
Time Limit: 2.0 Seconds   Memory Limit: 65536K
Total Runs: 485   Accepted Runs: 209    Multiple test files



FJ is going to teach his cows how to play a song. The song consists of N (1 ≤ N ≤ 50,000) notes, and the i-th note lasts for Bi (1 ≤ Bi ≤ 10,000) beats (thus no song is longer than 500,000,000 beats). The cows will begin playing the song at time 0; thus, they will play note 1 from time 0 through just before time B1, note 2 from time B1 through just before time B1 + B2, etc.

However, recently the cows have lost interest in the song, as they feel that it is too long and boring. Thus, to make sure his cows are paying attention, he asks them Q (1 ≤ Q ≤ 50,000) questions of the form, "In the interval from time T through just before time T+1, which note should you be playing?" The cows need your help to answer these questions which are supplied as Ti (0 ≤ Ti ≤ end_of_song).

Consider this song with three notes of durations 2, 1, and 3 beats:

Beat:   0    1    2    3    4    5    6    ...
        |----|----|----|----|----|----|--- ...
        1111111111     :              :
                  22222:              :
                       333333333333333:

Here is a set of five queries along with the resulting answer:

   Query    Note
     2        2
     3        3
     4        3
     0        1
     1        1

Input

* Line 1: Two space-separated integers: N and Q

* Lines 2..N+1: Line i+1 contains the single integer: Bi

* Lines N+2..N+Q+1: Line N+i+1 contains a single integer: Ti

Output

* Lines 1..Q: For each query, print a single integer that is the index of the note that the cows should be playing.

Sample Input

3 5
2
1
3
2
3
4
0
1

Sample Output

2
3
3
1
1



Source: USACO 2009 December Competition
Submit   List    Runs   Forum   Statistics

Tianjin University Online Judge v1.3.0
Maintance:Fxz. Developer: SuperHacker, G.D.Retop, Fxz