CTDL - set7 - Tổng trên set

Cho 1 dãy \(N\) số nguyên \(a_1, a_2, ... , a_N\) đôi một khác nhau, và một số nguyên dương \(K\).

Yêu cầu

Với mỗi giá trị \(i\) \((K \le i \le N)\), hãy in ra tổng của \(K\) phần tử lớn nhất trong đoạn từ \(1 → i.\)

Input

• Dòng đầu tiên chứa 2 số nguyên dương \(N,K\) \((1 \le K \le N \le 10^5)\).
• Dòng tiếp theo chứa \(N\) số nguyên \(a_1, a_2, ... , a_N\) \((|a_i| \le 10^9)\).

Output

In ra trên \(N − K + 1\) dòng, dòng thứ \(i\) \((K \le i \le N)\) là tổng của \(K\) phần tử lớn nhất trong đoạn \(1 → i.\)

Example

6 2
-3 5 4 6 -2 8

2
9
11
11
14

1 1
1

1

Gợi ý: Dùng một Set, luôn duy trì các phần tử của Set là K phần tử có tổng lớn nhất.