552. Sliding Window Median

0

Hard

The median is the middle value in a sorted list of integers. If the list has an even number of elements, there is no exact middle value. In this case, the median is the average of the two middle values. You are given an array of integers called 'nums' and an integer 'k'. A sliding window of size 'k' moves from the leftmost position of the array to the rightmost position. At each step, you can only see the 'k' numbers within the window. Your task is to print the median array for each window in the original array.

Input Format

The first line contains two space-separated integers, 'N' and 'K', representing the length of the array and the size of the sliding window, respectively. The second line contains 'N' space-separated integers, representing the elements of the array.

Output Format

Print the median array for each window.

Example

Input

8 3 2 4 3 5 8 1 2 1

Output

3 4 5 5 2 1

Constraints

1 <= k <= nums.length <= 10^5 -2^31 <= nums[i] <= 2^31 - 1