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.
• Dòng tiếp theo chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ - nội dung của mảng.

Output

• In ra ~n - k + 1~ giá trị: các trung vị

Constraints

• ~1 \leq k \leq n \leq 2 \times 10^5~
• ~1 \leq a_i \leq 10^9~.

Sample Test

Input:

8 3
2 4 3 5 8 1 2 1

Output:

3 4 5 5 2 1