Tiệc Kẹo Gậy

Nông dân John có $N$ con bò với chiều cao ban đầu lần lượt là $h_1,h_2,\dots ,h_N$ và $M$ cây kẹo gậy với chiều cao lần lượt là $c_1,c_2,\dots ,c_M$.

Nông dân John cho các con bò ăn kẹo gậy theo thứ tự từ cây kẹo thứ $1$ đến cây kẹo thứ $M$. Với mỗi cây kẹo gậy, ban đầu cây kẹo được treo thẳng đứng chạm đất (phần dưới ở vị trí $0$, phần trên ở vị trí bằng chiều cao cây kẹo). Các con bò lần lượt đến ăn theo thứ tự từ bò $1$ đến bò $N$. Mỗi con bò ăn phần kẹo từ vị trí thấp nhất còn lại của cây kẹo cho đến chiều cao hiện tại của nó (nếu chiều cao con bò lớn hơn phần thấp nhất còn lại). Sau khi ăn, chiều cao của con bò tăng thêm đúng bằng lượng kẹo đã ăn.

Hãy tính chiều cao cuối cùng của mỗi con bò sau khi tất cả $M$ cây kẹo đã được cho ăn.

Dữ liệu vào

• Dòng $1$: Hai số nguyên $N$ và $M$ ($1\le N,M\le 2·{10}^5$).
• Dòng $2$: $N$ số nguyên $h_1,h_2,\dots ,h_N$ ($1\le h_i\le {10}^9$) — chiều cao ban đầu của các con bò.
• Dòng $3$: $M$ số nguyên $c_1,c_2,\dots ,c_M$ ($1\le c_i\le {10}^9$) — chiều cao các cây kẹo gậy.

Dữ liệu ra

In ra $N$ dòng, dòng thứ $i$ là chiều cao cuối cùng của con bò thứ $i$.

Ràng buộc

• Các test $2$-$10$: $N,M\le {10}^3$.
• Các test $11$-$14$: Không có ràng buộc thêm.
• Lưu ý: Cần sử dụng kiểu dữ liệu 64-bit.

Ví dụ