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 ≤ i ≤ 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 ≤ K ≤ N ≤ 10^5)\).
• Dòng tiếp theo chứa \(N\) số nguyên \(a_1, a_2, ... , a_N\) \((|a_i| ≤ 10^9)\).

Output

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

Example

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.