Trung vị của cửa sổ

Cho mảng $n$ số và độ dài cửa sổ $k$. Với từng cửa sổ liên tiếp, in trung vị; khi $k$ chẵn, dùng trung vị nhỏ hơn trong hai phần tử giữa.

Cửa sổ thứ nhất là đoạn chỉ số $1,\dots ,k$, sau đó mỗi lần dịch sang phải đúng một vị trí. Nếu $k$ chẵn, trung vị được định nghĩa là phần tử thứ $k/2$ trong thứ tự không giảm.

Input

• Dòng đầu chứa $n$ $k$. Dòng thứ hai chứa $n$ số nguyên của mảng.

Output

• In $n-k+1$ trung vị theo thứ tự các cửa sổ từ trái sang phải.

Constraints

• $1\le k\le n\le 2\cdot 10^5$.
• Mỗi giá trị có độ lớn không vượt $10^9$.

Scoring

• Subtask small: $50$ điểm, gồm $10$ test nhỏ.
• Subtask full: $50$ điểm, gồm $10$ test không có giới hạn bổ sung ngoài phần Constraints.
• Mỗi test có giá trị $5$ điểm.

Example

7 4
8 1 5 2 9 3 6

2 2 3 3