Để giúp học sinh chuẩn bị tốt nhất cho kỳ thi, thầy Nam đã lên kế hoạch ôn tập cho các bạn học sinh để mỗi bạn sẽ đạt kết quả tốt nhất sau kỳ ôn tập đặc biệt này. Có ~n~ học sinh trong lớp học, bạn học sinh thứ ~i~ có năng lực ~a_i~. Thầy Nam xây dựng hệ thống gồm ~m~ bài tập, bài tập thứ ~j~ có độ khó ~b_j~. Với mỗi bạn, thầy sẽ có 1 lộ trình ôn tập riêng, mỗi bài tập sẽ chỉ làm 1 lần và học sinh chỉ có thể giải được bài thứ ~j~ khi có năng lực bằng hoặc lớn hơn ~b_j~. Nếu giải được bài thứ ~j~ năng lực của học sinh sẽ tăng thêm một lượng là ~b_j~.

Yêu cầu: Cho biết điểm năng lực của mỗi bạn học sinh sau khi kết thúc khoá ôn tập.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~m~ (~1 \le n, m \le 5 \times 10^5~).
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~1 \le a_i \le 10^9~) là năng lực của các bạn học sinh trong lớp học.
• Dòng thứ ba chứa ~m~ số nguyên ~b_1, b_2, ..., b_m~ (~1 \le b_j \le 10^9~) là độ khó của các bài tập trong kỳ ôn tập.

Output

Một dòng duy nhất là năng lực của các học sinh sau khoá ôn tập, mỗi số cách nhau 1 khoảng trắng.

Sample Input 1

4 3
7 3 2 5
6 4 16

Sample Output 1

33 3 2 15

Giải thích:

• Học sinh thứ 1: Năng lực 7. Giải được bài 6 (7 >= 6), năng lực 7 + 6 = 13. Giải được bài 4 (13 >= 4), năng lực 13 + 4 = 17. Giải được bài 16 (17 >= 16), năng lực 17 + 16 = 33.
• Học sinh thứ 2: Năng lực 3. Không giải được bài nào. Năng lực giữ nguyên là 3.
• Học sinh thứ 3: Năng lực 2. Không giải được bài nào. Năng lực giữ nguyên là 2.
• Học sinh thứ 4: Năng lực 5. Giải được bài 4 (5 >= 4), năng lực 5 + 4 = 9. Giải được bài 6 (9 >= 6), năng lực 9 + 6 = 15.

Ràng buộc

• 50% số test có ~n, m \le 10^3~.
• 50% số test còn lại không có ràng buộc gì thêm.