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 ≤ N ≤ 10^5) và K (1 ≤ K ≤ N).
• Dòng 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 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