Bạn được cho một mảng gồm \(n\) số nguyên. Nhiệm vụ của bạn là tính toán trung vị của mỗi đoạn con gồm \(k\) phần tử liên tiếp, từ trái sang phải.

Trung vị là phần tử ở giữa khi các phần tử được sắp xếp. Nếu số lượng phần tử là số chẵn, có thể có hai trung vị và chúng ta giả định rằng trung vị là số nhỏ hơn trong chúng.

Input

• Dòng đầu vào đầu tiên chứa hai số nguyên \(n\) và \(k\): số lượng phần tử và kích thước của đoạn con.
• Sau đó, có \(n\) số nguyên \(x_1, x_2, \ldots, x_n\): nội dung của mảng.

Output

• In \(n - k + 1\) giá trị: các trung vị.

Constraints

• \(1 \le k \le n \le 2 \cdot 10^5\)
• \(1 \le x_i \le 10^9\)

Example

Sample input

8 3
2 4 3 5 8 1 2 1

Sample output

3 4 5 5 2 1