LƯU Ý: Đội ngũ TGB quyết định sửa giới hạn của ~m~ thành ~2 \times 10^5~, khác với đề gốc (để phù hợp với kích thước dữ liệu nhập vào trên TGBOJ).

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 hệ thống lưu giữ nước từ các nguồn trên cao dổ 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ứ 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ự đế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ẽ sử 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.

Input

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

• Dòng đầu chứa hai số nguyên ~n~ và ~m~ (~1 \leq n \leq 2 \cdot 10^5~, ~1 \leq m \leq 2 \cdot 10^5~).

• Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~1 \leq a_i \leq 10^5~, ~1 \leq i \leq n~).

• Dòng thứ ba gồm ~m~ số nguyên ~r_1, r_2, ..., r_n~ (~1 \leq r_i \leq 10^5~, ~1 \leq i \leq m~).

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

Output

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 dương là lượng nước thu được ở từng máy xử lý nước. Nếu máy xử lý nước 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.

Scoring

Sample Input 1

4 5
6 8 2 5
4 3 2 7 6

Sample Output 1

14 6 1