Mirko and Slavko are known to play some games from time to time. 

N numbers appear on the screen in one minute intervals. A[1] will appear in first minute, and A[N] will appear in N-th minute. Screen has capacity of K numbers, that means that in each point in time, on the screen can be at most K numbers. After new number appears, number that appeared K minutes ago, if such exists, disappears. 

Aim of the game is to tell minimal absolute difference 2 distinct numbers on the screen in every minute. Slavko is very good at this game, help Mirko and tell him optimal results.

2 <= N <= 100 000

2 <= K <= 100 000

1 <= A[i] <= 100 000

Input

In the first line there are two numbers N and K, in the next line there are N integers describing array A.

Output

Output N-1 number, optimal result in each minute of the game.

Example

Input:
6 4

6 2 4 1 10 9

Output:
4 2 1 1 1

Explanation :

1st minute, on screen {6}
2nd minute, on screen {6, 2}, |6-2| = 4
3rd minute, on screen {6, 2, 4}, |6-4| = |4-2| = 2
4th minute, on screen {6, 2, 4, 1}, |2-1| = 1
5th minute, on screen {2, 4, 1, 10}, |2-1| = 1
6th minute, on screen {4, 1, 10, 9}, |10-9| = 1