Sau khi học lý thuyết ở trường, học sinh phải làm bài tập luyện tập. Thầy Minh đã xây dựng chương trình luyện tập trực tuyến trên Internet cho học sinh, thầy đã lên chương trình luyện tập cho ~N~ học sinh. Ban đầu, học sinh thứ ~i~ (~1 \le i \le N~) có kỹ năng làm bài tập là ~a_i~. Thầy Minh chuẩn bị ~M~ bài tập, bài thứ ~j~ (~1 \le j \le M~) có độ khó là ~b_j~. Thầy Minh chỉ định trình tự luyện tập các bài tập tùy thuộc vào kỹ năng làm bài tập ban đầu của từng học sinh và mỗi bài tập chỉ làm tối đa một lần để tránh nhàm chán. Để làm bài tập có độ khó ~x~, học sinh phải có kỹ năng làm bài tập không nhỏ hơn ~x~ và sau khi hoàn thành bài tập, kỹ năng làm bài tập của học sinh sẽ tăng thêm ~x~ đơn vị.

Để đánh giá tính hiệu quả của chương trình luyện tập, Thầy Minh cần biết kỹ năng làm bài tập cao nhất có thể của từng học sinh đạt được sau khi hoàn thành chương trình luyện tập.

Yêu cầu: Biết kỹ năng làm bài tập ban đầu của ~N~ học sinh và độ khó của ~M~ bài tập. Hãy tính kỹ năng làm bài tập cao nhất của từng học sinh đạt được sau khi hoàn thành chương trình luyện tập.

Input

• Dòng thứ nhất ghi 2 số nguyên dương ~N~ và ~M~ (~1 \le N, M \le 5 \times 10^5~) tương ứng là số lượng học sinh và số lượng bài tập;
• Dòng thứ hai ghi ~N~ số nguyên ~a_1, a_2, ..., a_N~ (~1 \le a_i \le 10^9, 1 \le i \le N~) tương ứng là kỹ năng làm bài tập ban đầu của từng học sinh;
• Dòng thứ ba ghi ~M~ số nguyên ~b_1, b_2, ..., b_M~ (~1 \le b_j \le 10^9, 1 \le j \le M~) tương ứng là độ khó của từng bài tập.
• Các số trên một dòng cách nhau một khoảng trắng.

Output

Xuất ra màn hình một dòng duy nhất chứa ~N~ số nguyên tương ứng là kỹ năng làm bài tập cao nhất của từng học sinh sau khi hoàn thành chương trình luyện tập, mỗi số cách nhau 1 khoảng trắng.

Sample Input 1

5 4
4 6 1 2 9
7 3 1 2 15

Sample Output 1

6 30 1 4 64

• Học sinh thứ nhất chỉ làm được bài tập số 3 được tăng kỹ năng làm bài tập ~4 + 2 = 6~.
• Học sinh thứ 2 lần lượt làm các bài tập số 3 được tăng kỹ năng làm bài tập ~6 + 2 = 8~, bài tập số 1 được tăng kỹ năng làm bài tập ~8 + 7 = 15~ và số 4 được tăng ~15 + 15 = 30~.
• Học sinh thứ 3 không làm được bài tập nào, kỹ năng làm bài tập là 1.
• Học sinh thứ 4 làm bài tập số 3 kỹ năng làm bài tập được tăng ~2 + 2 = 4~.
• Học sinh thứ 5 tương tự lần lượt làm các bài tập số 3, số 1, số 4 và số 2, kỹ năng làm bài tập là 64.

Subtasks

• Có 40% số test ứng với 40% số điểm thỏa mãn: ~M, N \le 10^3~;
• Có 20% số test khác ứng với 20% số điểm thỏa mãn: ~M, N \le 5 \cdot 10^4~;
• Có 40% số test còn lại ứng với 40% số điểm: không có ràng buộc gì thêm.