EIU Programming Practices and Exams

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 ai 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ố đó.

Example

Input:
3 5
2 5 6 4 7

Output:
7 8 9

Input:
3 5
2 6 6 3 7

Output:
7 9 8