Cho một dãy số gồm \(N\) số nguyên và một cửa sổ trượt kích thước \(K\). Với mỗi cửa sổ trượt khi di chuyển từ trái sang phải, hãy tìm số nguyên âm đầu tiên xuất hiện trong cửa sổ đó. Nếu trong cửa sổ trượt không chứa bất kỳ số nguyên âm nào, hãy ghi nhận giá trị là \(0\).

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên dương \(N\) và \(K\) (\(1 \le K \le N \le 10^5\)).
• Dòng hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(-10^9 \le a_i \le 10^9\)).

Định dạng đầu ra

• In ra \(N - K + 1\) số nguyên là số âm đầu tiên trong từng cửa sổ trượt, cách nhau bởi khoảng trắng.

Ví dụ

Input:

5 2
12 -1 -7 8 -15

Output:

-1 -1 -7 -15

Giải thích

• Cửa sổ \(\{12, -1\}\): số âm đầu tiên là -1.
• Cửa sổ \(\{-1, -7\}\): số âm đầu tiên là -1.
• Cửa sổ \(\{-7, 8\}\): số âm đầu tiên là -7.
• Cửa sổ \(\{8, -15\}\): số âm đầu tiên là -15.

Ràng buộc

• 30% số điểm ứng với \(N \le 1000\).
• 70% số điểm còn lại không có ràng buộc gì thêm.