Những chú bò của Farmer John rất hảo ngọt, và chúng đặc biệt thích ăn kẹo gậy! FJ có tổng cộng \(N\) con bò, mỗi con có một chiều cao ban đầu nhất định, và ông muốn cho chúng ăn \(M\) cây kẹo gậy, mỗi cây cũng có chiều cao khác nhau (\(1\le N,M\le 2\cdot 10^5\)).

FJ dự định lần lượt cho các con bò ăn từng cây kẹo gậy theo thứ tự được cho trong dữ liệu vào. Để cho chúng ăn một cây kẹo gậy, ông sẽ treo cây kẹo sao cho ban đầu nó vừa chạm mặt đất. Sau đó, các con bò lần lượt xếp hàng theo thứ tự trong dữ liệu vào và tiến đến cây kẹo; mỗi con ăn phần kẹo lên đến chiều cao của mình (vì nó không thể với cao hơn). Cây kẹo vẫn được treo cố định tại vị trí ban đầu và không được hạ xuống mặt đất, kể cả sau khi phần dưới của cây kẹo đã bị ăn. Có thể một con bò không ăn được gì trong lượt của mình nếu đáy phần kẹo còn lại đã cao hơn chiều cao của nó. Sau khi tất cả các con bò đã đến lượt, mỗi con cao thêm đúng bằng số đơn vị kẹo mà nó đã ăn. Farmer John treo cây kẹo tiếp theo và các con bò lặp lại quá trình (bò số 1 lại là con đầu tiên ăn cây kẹo mới).

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(M\).

Dòng tiếp theo chứa chiều cao ban đầu của \(N\) con bò, mỗi chiều cao thuộc đoạn \([1,10^9]\).

Dòng tiếp theo chứa chiều cao của \(M\) cây kẹo gậy, mỗi chiều cao thuộc đoạn \([1,10^9]\).

Dữ liệu ra

In chiều cao cuối cùng của mỗi con bò trên một dòng riêng.

Lưu ý rằng các số nguyên lớn trong bài này có thể đòi hỏi kiểu dữ liệu số nguyên 64 bit (ví dụ long long trong C/C++).

Ví dụ

3 2
3 2 5
6 1

7
2
7

Phân nhóm

• Dữ liệu 2–10: \(N,M\le 10^3\).
• Dữ liệu 11–14: Không có ràng buộc bổ sung.

Nguồn

USACO 2023 December Contest, Bronze — Candy Cane Feast: https://usaco.org/index.php?page=viewproblem2&cpid=1347

Tác giả bài toán: Agastya Goel