Cho mảng A gồm N số nguyên và một số K (1 ≤ K ≤ N). Hãy tính tổng các phần tử trong mỗi cửa sổ con liên tiếp có kích thước K.

Sử dụng kỹ thuật sliding window kết hợp queue: khi cửa sổ trượt sang phải, loại bỏ phần tử bên trái và thêm phần tử mới bên phải.

Đầu vào

• Dòng đầu tiên chứa hai số nguyên N (1 ≤ N ≤ 10^5) và K (1 ≤ K ≤ N).
• Dòng thứ hai chứa N số nguyên A_i (-10^3 ≤ A_i ≤ 10^3).

Đầu ra

In ra N - K + 1 số nguyên là tổng của từng cửa sổ, cách nhau bởi khoảng trắng.

Ví dụ

Input:
7 3
1 2 3 4 5 6 7

Output:
6 9 12 15 18