JOI đang chơi với một sợi dây dài \(N\), đặt thẳng từ trái sang phải. Dây gồm \(N\) đoạn nối liên tiếp; ban đầu mỗi đoạn dài \(1\), dày \(1\). Có tổng cộng \(M\) màu, và đoạn thứ \(i\) từ trái sang có màu \(C_i\).

JOI lặp lại thao tác sau cho tới khi dây còn dài \(2\). Gọi \(L\) là chiều dài hiện tại, chọn số nguyên \(j\) với \(1\le j<L\), rồi gập và ghép dây sao cho điểm cách đầu trái \(j\) đơn vị trở thành một đầu dây:

• Nếu \(j\le L/2\), với mỗi \(1\le i\le j\), ghép đoạn thứ \(i\) từ trái với đoạn thứ \(2j-i+1\). Đầu phải cũ vẫn là đầu phải, và chiều dài mới là \(L-j\).
• Nếu \(j>L/2\), với mỗi \(2j-L+1\le i\le j\), ghép đoạn thứ \(i\) từ trái với đoạn thứ \(2j-i+1\). Đầu trái cũ trở thành đầu phải, và chiều dài mới là \(j\).

Hai đoạn chỉ có thể ghép khi cùng màu. Trước khi ghép, JOI có thể đổi màu một đoạn với chi phí bằng độ dày của đoạn đó. Hai đoạn sau khi ghép trở thành một đoạn có độ dày bằng tổng độ dày ban đầu.

Với mỗi màu, hãy tính tổng chi phí nhỏ nhất để rút dây còn chiều dài \(2\) và trong hai đoạn cuối có một đoạn mang màu đó.

Dữ liệu vào

• Dòng đầu chứa \(N,M\).
• Dòng thứ hai chứa \(C_1,C_2,\ldots,C_N\).

Dữ liệu ra

In \(M\) dòng. Dòng thứ \(c\) chứa chi phí nhỏ nhất để dây cuối cùng có một đoạn màu \(c\).

Ràng buộc

• \(2\le N\le 1\,000\,000\).
• \(1\le M\le N\).
• \(1\le C_i\le M\).
• Với mỗi \(1\le c\le M\), tồn tại ít nhất một \(i\) sao cho \(C_i=c\).

Phân nhóm

1. \(15\) điểm: \(N\le 15\) và \(M\le 10\)
2. \(30\) điểm: \(N\le 100\,000\) và \(M\le 10\)
3. \(10\) điểm: \(N\le 100\,000\) và \(M\le 500\)
4. \(25\) điểm: \(M\le 5\,000\)
5. \(20\) điểm: Không có ràng buộc bổ sung

Ví dụ

5 3
1 2 3 3 2

2
1
1

7 3
1 2 2 1 3 3 3

2
2
2

10 3
2 2 1 1 3 3 2 1 1 2

3
3
4

Nguồn

JOI 2016/2017, Vòng chung kết.