Chia mảng thành k đoạn

Với một hằng số $m$ cho trước, độ đẹp của một mảng có ít nhất $m$ phần tử được định nghĩa là tổng của $m$ phần tử lớn nhất trong mảng đó.

Ví dụ, với $x=[4,3,1,5,2]$ và $m=3$, ba phần tử lớn nhất của $x$ là $5,4,3$ nên độ đẹp của $x$ bằng $5+4+3=12$.

Cho mảng $a_1,a_2,\dots ,a_n$, hằng số $m$ và số nguyên $k$. Hãy chia mảng $a$ thành đúng $k$ đoạn con liên tiếp sao cho:

• Mỗi phần tử của $a$ thuộc đúng một đoạn.
• Mỗi đoạn có ít nhất $m$ phần tử.
• Tổng độ đẹp của $k$ đoạn là lớn nhất có thể.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $m$, $k$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

• Dòng đầu in ra tổng độ đẹp lớn nhất.
• Dòng thứ hai in ra $k-1$ số nguyên $p_1,p_2,\dots ,p_{k-1}$ với $1\le p_1<p_2<\dots <p_{k-1}<n$, mô tả cách chia: đoạn thứ nhất gồm các phần tử từ vị trí $1$ đến $p_1$, đoạn thứ hai gồm các phần tử từ $p_1+1$ đến $p_2$, ..., đoạn thứ $k$ gồm các phần tử từ $p_{k-1}+1$ đến $n$.

Nếu có nhiều cách chia tối ưu, in ra bất kỳ cách nào.

Ràng buộc

• $2\le n\le 2·{10}^5$
• $1\le m$, $2\le k$, $m·k\le n$
• $-{10}^9\le a_i\le {10}^9$

Ví dụ