Đối với nhiều người, đại học là bước đánh dấu giai đoạn trưởng thành bắt đầu. Nếu như mái trường cấp ba luôn đem đến những ngày hồn nhiên, mơ mộng cùng biết kỉ niệm êm đềm, yên vui; mái trường đại học lại cho ta những góc xù xì, thô ráp của cuộc sống. Thời cấp ba, ta yên tâm sống trong vỏ bọc của gia đình, tha hồ đắm say trong bạn bè, bài vở và thầy cô. Còn khi tuổi 18 sang, ta thoát ra khỏi cái kén kia và tự mình đối mặt với những chông chênh của cuộc sống. Bởi thế, kể từ khi lên đại học, ta cần tự xây dựng chương trình học cho chính mình, còn nhà trường và thầy cô chỉ là những người tư vấn...

Ở một trường đại học nọ, nhà trường tổ chức giảng dạy ~n~ môn học. Các môn học được đánh số từ ~1~ đến ~n~. Để hoàn thành chương trình học, sinh viên không bắt buộc phải học hết cả ~n~ môn này. Sinh viên có thể đăng kí học hay bỏ bất kì môn nào, nhưng hoàn thành càng nhiều môn thì bằng tốt nghiệp sẽ càng ấn tượng. Chỉ có một ràng buộc duy nhất: Sinh viên phải học các môn theo thứ tự chỉ số tăng dần. Cụ thể, nếu một sinh viên đã quyết định sẽ học cả hai môn ~i~ và ~j~ với ~i < j~, bạn này sẽ phải học xong môn ~i~ trước khi bắt đầu học môn ~j~.

Là cố vấn học tập lâu năm, GS. PVH được nghe nhiều từ sinh viên về trải nghiệm khi học các môn ở trường. Từ đó, GS. PVH đánh giá rằng độ hấp dẫn của môn học thứ ~i~ là ~e_i~. Độ hấp dẫn của một môn học có thể là dương hoặc âm: có những môn khiến sinh viên tràn ngập niềm tin yêu vào cuộc sống (ví dụ như Triết học, Lịch sử Đảng hay Tư tưởng Hồ Chí Minh), nhưng cũng có nhiều môn khá "khoai" khiến nhiều sinh viên thấy áp lực và có phần nghẹt thở. Mỗi sinh viên sẽ có một chỉ số để đo "cảm hứng học tập" trong suốt 5 năm học tại trường. Khi học xong một môn nào, cảm hứng học tập của sinh viên sẽ tăng lên một lượng bằng độ hấp dẫn của môn đó. GS. PVH biết rằng, nếu cảm hứng học tập của một sinh viên xuống dưới ~0~, sinh viên đó sẽ ngập trong khủng hoảng và có thể dẫn tới trầm cảm, tự kỷ hay những sang chấn tâm lý khác. Vì vậy đây là điều cần tránh bằng mọi giá.

Năm học mới này, GS. PVH được giao làm cố vấn học tập cho ~m~ tân sinh viên. Thông qua cuộc trò chuyện đầu tiên, GS. PVH đánh giá cảm hứng học tập lúc mới vào trường của sinh viên thứ ~j~ là ~s_j~. GS. PVH cần tư vấn cho các sinh viên cách lựa chọn môn học. GS. PVH luôn muốn tất cả đều được học nhiều môn nhất có thể, nhưng cần đảm bảo rằng cảm hứng học tập của bất kì ai không bao giờ rơi xuống dưới ~0~ để ai cũng có một thời sinh viên đáng nhớ.

Do số tân sinh viên năm nay rất lớn, các bạn hãy giúp GS. PVH tính số môn học tối đa mỗi người có thể học nhé.

Input

Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ ~(1 \leq n \leq 2 \cdot 10^3, 1 \leq m \leq 3 \cdot 10^5)~, lần lượt là số môn học trong trường và số tân sinh viên GS. PVH nhận làm cố vấn.

Dòng thứ hai chứa ~n~ số nguyên ~e_1, e_2, \ldots, e_n~ ~(-10^9 \leq e_i \leq 10^9)~ thể hiện độ hấp dẫn của các môn học trong trường.

Dòng thứ ba chứa ~m~ số nguyên ~s_1, s_2, \ldots, s_m~ ~(0 \leq s_j \leq 2 \cdot 10^{12})~ thể hiện cảm hứng học tập của mỗi tân sinh viên ở thời điểm nhập trường.

Output

In ra ~m~ số nguyên trên một dòng, số thứ ~j~ thể hiện số môn tối đa tân sinh viên thứ ~j~ có thể học sao cho cảm hứng học tập không rơi xuống dưới ~0~ ở bất kì thời điểm nào.

Sắp tát

Bộ test của bài được chia làm các sắp tát như sau:

• Sắp tát ~1~ (~11~ điểm): Dãy ~e~ được sắp xếp tăng dần hoặc giảm dần. Nói cách khác, một trong hai điều sau là đúng: ~e_1 \leq e_2 \leq \ldots e_n~ hoặc ~e_1 \geq e_2 \geq \ldots \geq e_n~.
• Sắp tát ~2~ (~7~ điểm): ~n \leq 20~ và ~m \leq 30~
• Sắp tát ~3~ (~8~ điểm): ~n \leq 20~
• Sắp tát ~4~ (~19~ điểm): ~m \leq 3000~
• Sắp tát ~5~ (~25~ điểm): Không có ràng buộc gì thêm.

Điểm tối đa của bài là ~70~ điểm.

Ví dụ

Input 1

7 3
-3 0 4 -7 -4 -5 4 
2 11 15

Output 1

4 6 7

Input 2

8 4
-2 -2 0 7 1 -9 9 -7
1 1 20 3

Output 2

6 6 8 7

Giải thích

Trong ví dụ đầu tiên:

• Sinh viên thứ nhất chọn học các môn thứ ~2~, ~3~, ~6~, ~7~. Khi đó, cảm hứng học tập của sinh viên lúc nhập trường là ~2~, sau khi học các môn lần lượt là ~2 + 0 = 2~, ~2 + 4 = 6~, ~6 + (-5) = 1~ và ~1 + 4 = 5~. Như vậy, không khi nào cảm hứng học tập của bạn rơi xuống dưới ~0~.
• Sinh viên thứ hai chọn học tất cả các môn, trừ môn thứ ~5~. Khi đó, cảm hứng học tập của sinh viên lúc nhập trường là ~11~, sau khi học các môn lần lượt là ~11 + (-3) = 8~, ~8 + 0 = 8~, ~8 + 4 = 12~, ~12 + (-7) = 5~, ~5 + (-5) = 0~ và ~0 + 4 = 4~.