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\) (bánh trung thu), hộp bánh cấp \(i\) (\(i \geq 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 đa 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 \le j \le 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?

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\) (\(1 \le N,M \le 3 \times 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_i \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_j\) (\(1 \le X_j \le 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.

Output

• Gồm $M dòng, dòng thứ \(j\) in ra số lần mở hộp ít nhất để lấy được \(X_j\) bánh trung thu.

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(N,M \le 1000\).
• Subtask \(2\) (\(40\%\) số điểm): không có ràng buộc gì thêm.

Example

3 3
3 3 3
2 8 13

3
5
8