Music Notes

A farmer is teaching his cows to play a song. The song has $N$ notes ($1 \le N \le 50{,}000$), and the $i$-th note lasts $B_i$ beats ($1 \le B_i \le 10{,}000$), so the whole song is at most $500{,}000{,}000$ beats long.

The cows start playing at time $0$. They play note $1$ from time $0$ up to (but not including) time $B_1$, note $2$ from time $B_1$ up to time $B_1 + B_2$, and so on. In general, note $i$ is played during the half-open interval $[\,B_1 + \cdots + B_{i-1},\ B_1 + \cdots + B_i\,)$.

To keep the cows attentive, the farmer asks $Q$ questions ($1 \le Q \le 50{,}000$) of the form: “During the interval from time $T$ up to (but not including) time $T+1$, which note should you be playing?” Every query time $T$ ($0 \le T$) falls within the song, so exactly one note is being played.

For example, consider a song with three notes of durations $2$, $1$, and $3$ beats. The timeline looks like this:

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

Here note $1$ covers $[0, 2)$, note $2$ covers $[2, 3)$, and note $3$ covers $[3, 6)$.

• Line 1: two space-separated integers $N$ and $Q$.
• Lines $2 \ldots N+1$: line $i+1$ contains a single integer $B_i$.
• Lines $N+2 \ldots N+Q+1$: line $N+i+1$ contains a single integer $T_i$, the $i$-th query time.

• Lines $1 \ldots Q$: for each query, print a single integer — the $1$-based index of the note that is being played during that query interval.