A window of fixed width slides along a list one position at a time. Report the lower median of each window: the middle value when the width is odd, and the smaller of the two middle values when it is even.

Sorting each window from scratch throws away almost everything the last one told you, since only one value leaves and one arrives. Two heaps facing each other, one holding the lower half and one the upper, is what turns each step into a couple of adjustments.

Input

The window width on the first line, then the count and the values.

Output

One median per window, space separated.

Sample test cases

Input 3 8 1 3 -1 -3 5 3 6 7

Expected output 1 -1 -1 3 5 6

Input 2 3 1 2 3

Expected output 1 2