Cho mảng A gồm N số nguyên (có thể âm). Với mỗi cửa sổ con liên tiếp có kích thước K, hãy tìm số âm đầu tiên trong cửa sổ đó. Nếu không có số âm nào, in ra 0.

Sử dụng queue để lưu chỉ số các phần tử âm trong cửa sổ hiện tạ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, mỗi số là số âm đầu tiên trong cửa sổ tương ứng hoặc 0 nếu không có.

Ví dụ

Input:
8 3
2 -1 3 -2 5 4 -1 6

Output:
-1 -1 -2 -2 0 -1

Ràng buộc & Subtasks