atcoder#ABC281E. [ABC281E] Least Elements

[ABC281E] Least Elements

Score : 500500 points

Problem Statement

You are given an integer sequence A=(A1,,AN)A = (A_1, \dots, A_N) of length NN, and integers MM and KK. For each i=1,,NM+1i = 1, \dots, N - M + 1, solve the following independent problem.

Find the sum of the first KK values in the sorted list of the MM integers Ai,Ai+1,,Ai+M1A_i, A_{i + 1}, \dots, A_{i + M - 1} in ascending order.

Constraints

  • 1KMN2×1051 \leq K \leq M \leq N \leq 2 \times 10^5
  • 1Ai1091 \leq A_i \leq 10^9
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

NN MM KK

A1A_1 A2A_2 \ldots ANA_N

Output

Let answerk\mathrm{answer}_k be the answer to the problem for i=ki = k, and print them in the following format:

answer1\mathrm{answer}_1 answer2\mathrm{answer}_2 \ldots answerNM+1\mathrm{answer}_{N-M+1}

6 4 3
3 1 4 1 5 9
5 6 10
  • For i=1i = 1, sorting Ai,Ai+1,Ai+2,Ai+3A_i, A_{i+1}, A_{i+2}, A_{i+3} in ascending order yields 1,1,3,41, 1, 3, 4, where the sum of the first three values is 55.
  • For i=2i = 2, sorting Ai,Ai+1,Ai+2,Ai+3A_i, A_{i+1}, A_{i+2}, A_{i+3} in ascending order yields 1,1,4,51, 1, 4, 5, where the sum of the first three values is 66.
  • For i=3i = 3, sorting Ai,Ai+1,Ai+2,Ai+3A_i, A_{i+1}, A_{i+2}, A_{i+3} in ascending order yields 1,4,5,91, 4, 5, 9, where the sum of the first three values is 1010.
10 6 3
12 2 17 11 19 8 4 3 6 20
21 14 15 13 13