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

Ràng buộc & Subtasks