Trên một con đường có \(m\) trạm xăng (trạm \(1\), \(2\), ..., \(m\)), \(n\) xe ô tô đều xuất phát từ trạm \(1\). Bạn hãy lập trình tính xem có bao nhiêu xe dừng ở mỗi trạm xăng, biết rằng:

• Mỗi cây xăng đều chỉ cung cấp một lượng xăng tối đa nào đó.
• Đi hết \(1\) đơn vị độ dài tốn đúng \(1\) đơn vị lượng xăng.
• Các xe trước khi xuất phát từ trạm nào đều nạp một lượng xăng tối đa ở trạm đó.
• Các xe chỉ rời trạm khi đã đủ xăng đi tới trạm tiếp theo.

Chú ý: Nếu các xe đều có thể đi qua trạm cuối, ta vẫn tính là dừng ở trạm cuối.

Đầu vào

Dòng đầu tiên gồm hai số tự nhiên \(m, n\) \((2 \le m, n \le 10^5)\), số trạm và số xe ô tô (xuất phát từ trạm \(1\)) cần khảo sát.

Dòng thứ hai chứa \(m\) số tự nhiên không quá \(10^9\), số thứ \(i\) \((1 \le i \le m)\) là số xăng tối đa trạm thứ \(i\) có thể cung cấp cho một xe.

Dòng thứ ba chứa \(m - 1\) số tự nhiên không quá \(10^9\), số thứ \(i\) \((1 \le i \le m - 1)\) là khoảng cách từ trạm thứ \(i\) tới trạm thứ \(i + 1\).

Dòng cuối cùng chứa \(n\) số tự nhiên không quá \(10^9\) là lượng xăng của các xe ô tô.

Đầu ra

Một dòng duy nhất chứa \(m\) số tự nhiên, số thứ \(i\) là số lượng xe dừng ở trạm \(i\).

Subtask

\(30\%\) số test có \(m*n \le 10^6\).

Ví dụ

Đầu vào:

5 5
1 0 1 0 1
1 1 1 1
0 1 2 3 4

Đầu ra:

0 1 0 1 3

Giải thích: Xe thứ nhất dừng ở trạm \(2\), xe thứ hai dừng ở trạm \(4\), ba xe còn lại đều có thể đi qua trạm cuối.