Một nhà phân tích tài chính đang nghiên cứu biến động giá cổ phiếu của một công ty trong N ngày, mỗi ngày có giá \(A_i\). Ông ta muốn xem xét các cửa sổ thời gian liên tiếp có độ dài K và tính giá trị trung vị của mỗi cửa sổ để đánh giá xu hướng ngắn hạn.

Cụ thể, với mỗi vị trí i từ 1 đến N–K+1, xét đoạn \(A_i\)..A_{i+K-1}, hãy tìm phần tử đứng ở vị trí thứ (K+1)/2 sau khi sắp xếp (gọi là median). Với K lẻ, median là phần tử chính giữa; với K chẵn, median là phần tử thứ K/2 từ trái sang.

Đầu vào

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

Đầu ra

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

Ví dụ

Input:
8 4
5 3 8 1 7 9 2 6

Output:
3 3 7 7 6

Ràng buộc & Subtasks