Xác định cụm chứa mã thứ tự

Bối cảnh và bài toán

Có n cụm dữ liệu theo thứ tự. Cụm i chứa a[i] bản ghi và các bản ghi toàn hệ thống được đánh số liên tục từ 1. Với mỗi mã thứ tự toàn cục q, cần xác định bản ghi đó thuộc cụm nào.

Yêu cầu

Với mỗi truy vấn q, in chỉ số cụm chứa vị trí q.

Input

• Dòng 1: n.
• Dòng 2: kích thước a[i] của n cụm.
• Dòng 3: m số truy vấn.
• Dòng 4: m giá trị q.

Output

In chỉ số cụm cho từng q.

Ràng buộc

• 1 <= n, m <= 10^5
• 1 <= a[i] <= 10^3
• 1 <= q <= sum(a[i])

Chấm điểm

Ví dụ 1

Input

5
2 7 3 4 9
3
1 25 11

Output

1
5
3

Giải thích. Các mốc kết thúc của năm cụm lần lượt là 2,9,12,16,25; vị trí 11 nằm sau mốc 9 và không vượt mốc 12, nên thuộc cụm 3.

Ví dụ 2

Input

4
1 1 1 1
4
1 2 3 4

Output

1
2
3
4

Giải thích. Mỗi cụm có đúng một phần tử.

Thông tin bài tập

Nguồn: Phỏng theo Codeforces 474B — Worms.

Tham khảo: https://codeforces.com/problemset/problem/474/B