Để chuẩn bị cho giải đấu sắp tới, huấn luyện viên (HLV) lên giáo án luyện tập để nâng cao kỹ năng thi đấu của n vận động viên (VĐV). Ban đầu, VĐV thứ \(i\) có kỹ năng thi đấu là \(a_i\).

HLV chuẩn bị \(m\) bài tập, bài tập thứ \(j\) có độ khó là \(b_j\). HLV chỉ định trình tự luyện tập các bài cho VĐV tùy vào kỹ năng thi đấu ban đầu của và mỗi bài tập chỉ tập tối đa 1 lần để tránh nhàm chán. Để thực hiện bài có độ khó là \(x\), VĐV phải có kỹ năng thi đấu không nhỏ hơn \(x\) và sau khi hoàn thành, kỹ năng thi đấu của VĐV tăng thêm \(x\) đơn vị. Để đánh giá tính hiệu quả của giáo án, HLV cần biết kỹ năng thi đấu cao nhất của từng VĐV đạt được sau đợt tập huấn.

Yêu cầu: Cho kỹ năng thi đấu ban đầu của \(n\) VĐV và độ khó của \(m\) bài tập. Hãy cho biết kỹ năng thi đấu của từng VĐV sau đợt tập huấn.

Dữ liệu Vào từ file văn bản TRAINING.INP có cấu trúc:

• Dòng đầu chứa 2 số nguyên dương \(n\) và \(m (1≤n,m≤5×10^5 )\).

• Dòng thứ hai chứa \(n\) số \(a_1,a_2,…,a_n (1≤a_i≤10^9 ).\)

• Dòng thứ ba ghi \(m\) số \(b_1,b_2,…,b_m (1≤b_j ≤10^9).\)

Kết quả ghi vào file văn bản TRAINING.OUT có cấu trúc:

• Ghi một dãy số nguyên là kỹ năng thi đấu cao nhất của các VĐV sau đợt tập huấn.

Ràng buộc

• Subtask 1 (40% số điểm): \(n,m≤1000.\)

• Subtask 2 (30% số điểm): \(n,m≤5×10^4.\)

• Subtask 3 (30% số điểm): không có ràng buộc gì thêm.

Sample Input

5 4
4 6 1 2 9
7 31 2 15

Sample Output

6 30 1 4 64