Những con sâu (Worms)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $n$ đống sâu được xếp theo thứ tự. Đống thứ $i$ chứa $a_i$ con sâu.

Tất cả sâu được đánh số liên tiếp:

• đống $1$ chứa các nhãn từ $1$ đến $a_1$;
• đống $2$ tiếp tục từ $a_1+1$;
• và cứ như vậy cho đến đống $n$.

Có $m$ nhãn sâu cần tra cứu. Với mỗi nhãn $q_j$, hãy cho biết con sâu đó nằm trong đống số mấy.

Input

Dòng đầu chứa $n$.

Dòng thứ hai chứa $a_1,a_2,\ldots,a_n$.

Dòng thứ ba chứa $m$.

Dòng thứ tư chứa $q_1,q_2,\ldots,q_m$.

Output

Với mỗi truy vấn, in một dòng là số thứ tự đống chứa con sâu có nhãn tương ứng.

Subtask

• Subtask 1 — 20%: $1\le n,m\le100$.
• Subtask 2 — 30%: $1\le n,m\le5000$.
• Subtask 3 — 50%: $1\le n,m\le10^5$, $1\le a_i\le10^3$, $\sum a_i\le10^6$, $1\le q_j\le\sum a_i$.

Ví dụ

Input

5
2 7 3 4 9
3
1 25 11

Output

1
5
3

Giải thích

Tổng số sâu tính đến từng đống là:

Do đó:

• nhãn $1$ thuộc đống $1$ vì $1\le2$;
• nhãn $25$ thuộc đống $5$ vì $16<25\le25$;
• nhãn $11$ thuộc đống $3$ vì $9<11\le12$.

Vì vậy ba đáp án lần lượt là $1,5,3$.