Busy Beaver đang tạo ra một ngôn ngữ mới cho lớp ngôn ngữ học của mình! Cậu ấy đã quyết định rằng ngôn ngữ của mình sẽ có một bảng chữ cái gồm các chữ cái là các số nguyên $1, \dots, NM$ theo thứ tự đó; bây giờ cậu ấy muốn tạo ra một số từ cho ngôn ngữ này.

Vì Busy Beaver quan tâm đến thống kê, cậu ấy muốn kiểm soát tần suất xuất hiện của các chữ cái trong các từ, vì vậy cậu ấy đã chọn một đa tập hợp $a$ có kích thước $NM$ gồm các chữ cái từ bảng chữ cái của mình. Bây giờ cậu ấy sẽ tạo ra $N$ từ, mỗi từ có $M$ chữ cái sao cho mỗi chữ cái từ $a$ được sử dụng đúng một lần (tức là nếu một chữ cái $x$ cho trước xuất hiện đúng $k$ lần trong $a$, thì nó được sử dụng đúng $k$ lần trong tất cả $N$ từ).

Sau khi tạo các từ, Busy Beaver dự định sắp xếp chúng vào một từ điển, vì vậy cậu ấy sẽ sắp xếp $N$ từ của mình theo thứ tự từ điển để tạo ra dãy các từ $s_1, \dots, s_N$. Busy Beaver thích các chuỗi có thứ tự từ điển nhỏ, vì vậy với mỗi $k$ từ $1$ đến $N$, cậu ấy muốn biết giá trị nhỏ nhất có thể theo thứ tự từ điển của $s_k$ dựa trên tất cả các cách chọn từ.

Lưu ý rằng câu trả lời cho mỗi $s_k$ là độc lập; ví dụ, cách chọn các từ để $s_1$ nhỏ nhất có thể khác với cách chọn các từ để $s_2$ nhỏ nhất.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên dương $N, M$ ($1 \le NM \le 10^6$). Dòng thứ hai chứa $NM$ số nguyên $a_1, \dots, a_{NM}$ tạo thành đa tập hợp $a$ ($1 \le a_j \le NM$).

Dữ liệu ra

Với mỗi $k$ từ $1$ đến $N$, hãy in ra giá trị nhỏ nhất có thể của $s_k$ trên một dòng riêng biệt dưới dạng một dãy các số nguyên cách nhau bởi dấu cách.

Ví dụ

Ví dụ 1

4 3
1 1 2 2 3 3 4 4 5 5 6 6

1 1 2
1 2 3
2 2 3
2 3 4

Ví dụ 2

3 4
12 4 4 4 1 1 4 4 6 4 1 4

1 1 1 4
1 4 4 4
1 4 4 12

Ví dụ 3

4 5
12 7 17 3 6 11 9 2 17 7 1 6 9 12 6 3 9 12 2 15

1 2 2 3 3
2 2 3 3 6
2 3 6 7 7
3 3 6 6 6

Ví dụ 4

1 1
1

1

Ghi chú

Trong ví dụ đầu tiên, các cách chọn từ sau đây giúp tối thiểu hóa mỗi $s_k$: Bằng cách chọn các từ 112, 233, 445, 566, ta có $s = 112, 233, 445, 566$, do đó $s_1 = 112$ như mong muốn. Bằng cách chọn các từ 123, 456, 123, 456, ta có $s = 123, 123, 456, 456$, do đó $s_2 = 123$ như mong muốn. Bằng cách chọn các từ 166, 155, 344, 223, ta có $s = 155, 166, 223, 344$, do đó $s_3 = 223$ như mong muốn. Bằng cách chọn các từ 234, 234, 156, 156, ta có $s = 156, 156, 234, 234$, do đó $s_4 = 234$ như mong muốn. Có thể chứng minh rằng trong tất cả các trường hợp này, không có cách nào để chọn các từ sao cho $s_k$ tương ứng nhỏ hơn nữa theo thứ tự từ điển.