Cho một mảng A gồm N số nguyên và một số K (1 ≤ K ≤ N). Hãy tìm giá trị lớn nhất trong mỗi cửa sổ trượt có kích thước K.

Sử dụng deque (hàng đợi hai đầu) để duy trì các chỉ số của các phần tử trong cửa sổ theo thứ tự giảm dần giá trị. Phần tử ở đầu deque luôn là phần tử lớn nhất 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^9 ≤ A_i ≤ 10^9).

Đầu ra

In ra N - K + 1 số nguyên, mỗi số là giá trị lớn nhất của cửa sổ tương ứng, cách nhau bởi khoảng trắng.

Ví dụ

Input:
8 3
1 3 -1 -3 5 3 6 7

Output:
3 3 5 5 6 7