Trên một vùng núi, người dân tự thiết kế mô hình xử lý nước uống cho các hộ dân vùng cao. Họ đặt ~n~ hệ thống lưu giữ nước từ các nguồn trên cao đổ về. Lượng nước đưa vào ~n~ hệ thống lần lượt là ~a_1, a_2,..., a_n~ (lít).

Các hệ thống có cấu tạo giống nhau. Mỗi hệ thống có ~m~ bồn chứa nước được đánh số từ ~1, 2, ..., m~ với dung tích lần lượt là ~r_1, r_2,..., r_m~ (lít). Bồn chứa nước số ~1~ được đặt ở vị trí cao nhất, tiếp đến là bồn số ~2~,... và thấp nhất là bồn số m. Do đó, khi nước vào hệ thống, nước sẽ chảy vào bồn số ~1~ trước, chỉ khi nào đẩy bồn số ~1~, nước mới chảy tiếp qua bồn số ~2~, tương tự cho đến bồn số ~m~.

Đồng thời, họ xây dựng ~m~ máy xử lý nước uống. Sau khi các hệ thống đã lưu giữ nước vào các bồn chứa. Máy xử lý nước số ~1~ sẽ xử lý nước từ các bồn chứa số ~1~ của tất cả các hệ thống lưu giữ. Tương tự cho các máy xử lý nước còn lại.

Yêu cầu: Hãy viết chương trình tính lượng nước thu được trong từng máy xử lý nước.

Hình minh họa có ~4~ hệ thống (mỗi hệ thống có ~5~ bồn chứa) và ~5~ máy xử lý nước.

Dữ liệu

Vào từ file văn bản LOCNUOC.INP gồm ~3~ dòng:

• Dòng đầu tiên chứa ~2~ số ~n~ và ~m~ ~(1 \le n \le 2 \times 10^5, 1 \le m \le 10^9)~
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le 10^5, 1 \le i \le n)~
• Dòng thứ hai chứa ~m~ số nguyên ~r_1, r_2, ..., r_m~ ~(1 \le r_i \le 10^5, 1 \le i \le m)~

Các số trên cùng một dòng cách nhau một khoảng trắng.

Kết quả

• Ghi ra file văn bản LOCNUOC.OUT một dòng duy nhất gồm tối đa ~m~ số nguyên là lượng nước thu được ở từng máy xử lý có nước. Nếu máy xử lý không nhận được nước thì không in ra. Các số trên cùng một dòng cách nhau một khoảng trắng.

Ràng buộc

• Chương trình thực thi giới hạn trong ~1~ giây.
• ~40\%~ số điểm của bài: ~1 \le n \le 10^3, 1 \le m \le 10^2~.
• ~30\%~ số điểm của bài: ~1 \le n \le 10^3, 1 \le m \le 10^9~.
• ~30\%~ số điểm của bài: ~1 \le n \le 2 \times 10^5, 1 \le m \le 10^9~.

Ví dụ

Dữ liệu

4 5 
6 8 2 5
4 3 2 7 6

Kết quả

14 6 1

Giải thích

• Lượng nước của ~4~ hệ thống lần lượt là ~6, 8, 2, 5~ lít.
• Dung tích của ~5~ bồn chứa nước lần lượt là ~4, 3, 2, 7, 6~ lít.
• Các bồn chứa nước số ~1~: hệ thống ~1, 2~ và ~4~ nhận được ~4 \times 3 = 12~ lít, riêng hệ thống ~3~ chỉ nhận được ~2~ lít. Vậy, máy xử lý nước số ~1~ nhận được ~12 + 2 = 14~ lít. Lượng nước còn lại ở các hệ thống sẽ là ~2, 4, 0, 1~ lít.
• Các bồn chứa nước số ~2~ của ~4~ hệ thống lần lượt nhận được ~2, 3, 0, 1~ lít. Vậy, máy xử lý nước số ~2~ nhận được ~6~ lít. Vậy, máy xử lý nước số ~2~ nhận được ~6~ lít. Lượng nước còn lại ở các hệ thống sẽ là ~0, 1, 0, 0~ lít.
• Các bồn chứa nước số ~3~ của ~4~ hệ thống lần lượt nhận được ~0, 1, 0, 0~ lít. Vậy, máy xử lý nước số ~3~ nhận được ~1~ lít. Lượng nước còn lại ở các hệ thống sẽ là ~0, 0, 0, 0~ lít.
• Các bồn chứa nước số ~4, 5~ không có nược. Vậy, máy xử lý nước số ~4, 5~ không nhận được nước nên không in ra.