Cho một dãy gồm \(N\) số nguyên \(A_1, A_2, \dots, A_N\) và một số nguyên dương \(K\) (\(K \le N\)). Với mỗi ô cửa sổ trượt kích thước \(K\) từ trái sang phải, ta có các phần tử trong cửa sổ là \(A_i, A_{i+1}, \dots, A_{i+K-1}\).

Nhiệm vụ của bạn là tìm số trung vị (median) của mỗi ô cửa sổ trượt này.

Định nghĩa số trung vị của một dãy gồm \(K\) phần tử sau khi đã sắp xếp tăng dần:

• Nếu \(K\) lẻ, số trung vị là phần tử đứng ở vị trí thứ \((K+1)/2\) (1-indexed).
• Nếu \(K\) chẵn, số trung vị là phần tử đứng ở vị trí thứ \(K/2\) (1-indexed).

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên dương \(N\) và \(K\) (\(1 \le K \le N \le 2 \cdot 10^5\)).
• Dòng hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(1 \le A_i \le 10^9\)).

Định dạng đầu ra

• In ra \(N - K + 1\) số nguyên trên một dòng duy nhất, cách nhau bởi một khoảng trắng, tương ứng là số trung vị của các cửa sổ trượt theo thứ tự từ trái sang phải.

Ràng buộc & Subtasks

• Subtask 1 (30% số điểm): \(N \le 1000\).
• Subtask 2 (30% số điểm): \(K \le 100\).
• Subtask 3 (40% số điểm): \(N \le 2 \cdot 10^5\), các ràng buộc gốc.

Ví dụ

Input:

8 3
2 4 3 5 8 1 2 1

Input:

3 4 5 5 2 1

Giải thích:

• Cửa sổ 1: \([2, 4, 3]\) sắp xếp thành \([2, 3, 4] \to\) trung vị là 3.
• Cửa sổ 2: \([4, 3, 5]\) sắp xếp thành \([3, 4, 5] \to\) trung vị là 4.
• Cửa sổ 3: \([3, 5, 8]\) sắp xếp thành \([3, 5, 8] \to\) trung vị là 5.
• Cửa sổ 4: \([5, 8, 1]\) sắp xếp thành \([1, 5, 8] \to\) trung vị là 5.
• Cửa sổ 5: \([8, 1, 2]\) sắp xếp thành \([1, 2, 8] \to\) trung vị là 2.
• Cửa sổ 6: \([1, 2, 1]\) sắp xếp thành \([1, 1, 2] \to\) trung vị là 1.