Bài toán phân công công việc là một bài toán rất phổ biến trong cuộc sống. Xét một dạng cơ bản như sau: có ~n~ người và ~m~ công việc, mỗi người có năng suất làm việc như nhau và công việc thứ ~i~ cần ~a_i~ thời gian để một người thực hiện, mỗi công việc chỉ giao cho ~1~ người. Một trong những thuật toán đơn giản để thực hiện việc phân công này là:

• B1: Sắp xếp các công việc theo thời gian hoàn thành.

• B2: phân công việc có thời gian thực hiện lớn nhất chưa giao cho người làm ít thời gian nhất (tổng thời gian các công việc được giao là nhỏ nhất).

• B3: nếu mọi công việc được giao thì kết thúc, ngược lại quay lại bước 2.

Input

• Dòng đầu tiên là 2 số nguyên n, m (n, m <= ~10^{5}~).

• Dòng thứ 2 là m số nguyên dương không vượt quá ~10^{5}~ là thời gian thực hiện của m công việc tương ứng.

Output

• 1 dòng gồm n số nguyên lần lượt là thời gian làm việc của n người.

Lưu ý: ở bước 2, nếu có nhiều hơn 1 người có thời gian làm việc ít nhất thì chọn người có thứ tự nhỏ nhất trong số đó.

Sample Input:

3 5
2 5 6 4 7

Sample Output:

7 8 9

Sample Input:

3 5
2 6 6 3 7

Sample Output:

7 9 8