RIOI_3_4 - Cheaters

no tags 

 

Mirko and Slakvo 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, can you help Mirko and tell him optimal results

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


Added by:Buda IM
Date:2012-12-08
Time limit:0.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC ASM64 MAWK BC C-CLANG NCSHARP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Own problem