Dựa trên ý tưởng của búp bê Nga Matrioska, công ty bánh Trung Thu có sản xuất những hộp bánh đặc biệt như sau:

Trong một hộp bánh có thể chứa những hộp bánh nhỏ hơn, hộp bánh nhỏ nhất sẽ chứa bánh trung thu. Giả sử bánh trung thu là hộp bánh cấp ~0~, hộp bánh cấp ~1~ sẽ chứa những hộp bánh cấp ~0~ (bánh trung thu), hộp bánh cấp ~i (i ≥ 1)~ sẽ chứa ~a_i~, hộp bánh cấp ~i-1~. Thấy ý tưởng rất độc đáo nên Bờm cũng đã mua một hộp bánh cấp ~N~ về để mở tiệc trung thu cho các bạn nhỏ. Bờm muốn biết số lần mở hộp ít nhất để lấy được ~X~ chiếc bánh trung thu. Vì Bờm vẫn chưa biết có bao nhiêu bạn nhỏ tham gia tiệc trung thu nên để không tốn thời gian tính toán, Bờm sẽ chuẩn bị trước nhiều phương án.

Yêu cầu: Cho ~M~ phương án, với phương án thứ ~j (1 ≤ j ≤ M)~ cần ~X_j~ bánh trung thu, bạn hãy giúp Bờm tính xem cần ít nhất bao nhiêu lần mở hộp?

Dữ liệu: Vào từ thiết bị vào chuẩn theo khuôn dạng sau:

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~ ~(1 \le N,M \le 3.10^5)~ là cấp của hộp bánh của Bờm và số phương án cần tính toán.

• Dòng thứ hai chứa ~N~ số nguyên ~a_i~ ~(1 \le a \le 10^9 ; 1\le i \le N)~ mô tả hộp bánh cấp ~i~ sẽ chứa ~a_i~, hộp bánh cấp ~i-1~.

• Dòng thứ ba chứa ~M~ số nguyên ~X~, ~(1≤X≤10^{12};1\le j \le M)~ tương ứng với số bánh trung thu cần lấy ra trong mỗi phương án.

Kết quả: Ghi ra thiết bị ra chuẩn gồm ~M~ dòng, dòng thứ ~j~ in ra số lần mở hộp ít nhất để lấy được ~X~ bánh trung thu.

Sample Input

3 3
3 3 3
2 8 13

Sample Output

3
5
8

Giải thích ví dụ:

Hộp bánh cấp ~1~ có ~3~ bánh trung thu. Hộp bánh cấp ~2~ chứa ~3~ hộp bánh cấp ~1~. Hộp bánh cấp ~3~ chứa ~3~ hộp bánh cấp ~2~.

• Giả sử, để lấy được ~2~ bánh trung thu thì phải mở ~1~ hộp bánh cấp ~3~, được ~3~ hộp bánh cấp ~2~. Sau đó, mở ~1~ hộp bánh cấp ~2~, được ~3~ hộp bánh cấp ~1~. Tiếp theo, mở ~1~ hộp bánh cấp ~1~, được ~3~ bánh trung thu. Vậy phải mở hộp ~3~ lần.

• Giả sử, để lấy ~8~ bánh trung thu thì mở ~1~ hộp bánh cấp ~3~, được ~3~ hộp bánh cấp ~2~. Sau đó, mở ~1~ hộp bánh cấp ~2~, được ~3~ hộp cấp ~1~. Tiếp theo, mở ~3~ hộp bánh cấp ~1~, được ~9~ bánh trung thu. Vậy phải mở hộp ~5~ lần.

Ràng buộc:

• Có ~60~% số lượng test ứng với ~60~% số điểm có ~N,M ≤ 1000~;

• Có ~40~% số lượng test còn lại với ~40~% số điểm không có ràng buộc thêm.