THPT Chuyên Bến Tre

* Chú ý: do dung lượng test quá lớn không up lên server được, chỉ được khoảng 50% test, đề nghị các em HS nộp bài cho thầy cô lãnh đội để gửi về ban tổ chức chấm test đầy đủ, tên bài là LT.PAS, file input là LT.INP, file output là LT.OUT, chuyển vào thư mục có tên thư mục là nick spoj của HS. Nếu HS ko nộp bài thì kết quả chỉ bằng số điểm chấm online.

Hôm nay, các thầy cô tổ chức thi lập trình đồng đội giữa các lớp trong nhà trường. Có tất cả N đội tham gia, mỗi đội sẽ có M thành viên, mỗi thành viên tham gia có một chỉ số về kỹ năng lập trình. Ban tổ chức xếp N đội thi đấu theo một vòng tròn và đánh thứ tự lần lượt các đội là 1, 2, …, N.

Đội i có thể thắng được đội j nếu thỏa mãn hai điều kiện sau:

- Tổng chỉ số kỹ năng lập trình đội i lớn hơn tổng chỉ số kỹ năng lập trình đội j

- Giữa đoạn [i,j] không có đội nào có tổng chỉ số kỹ năng lập trình lớn hơn hoặc bằng tổng chỉ số kỹ năng lập trình của đội i.

Cho trước chỉ số kỹ năng lập trình của các bạn học sinh, hãy cho biết mỗi đội có thể thắng được bao nhiêu đội khác trong cuộc thi này.

Input

• Dòng 1: Gồm hai số M (1 ≤ M ≤ 10) và N (2 ≤ N ≤ 500.000)
• M dòng tiếp theo, mỗi dòng chưa N số A[u,v] (0 ≤ A[u,v] ≤ 1000.000) – chỉ số kỹ năng lập trình của thành viên u trong đội v.

Output

• Gồm N số, trong đó số thứ k có giá trị t cho biết đội k có thể thắng được t đội.

Example

Input:
3 6
4 3 6 1 6 2
4 1 5 2 7 3
5 6 2 7 8 1

Output:
2 0 2 0 5 0

* Giải thích:

Đội 1: thắng đội 2 và đôi 6
Đội 2: Không thắng đội nào
Đội 3: thắng đội 2 và 4
Đội 4: không thắng đội nào
Đội 5: thắng đội 1, 2, 3, 4, 6
Đội 6: không thắng đội nào