You are given a permutation P_1 ... P_N of the set {1, 2, ..., N}.

You can apply the following operation to this permutation, any number of times (possibly zero):

* Choose two indices i,j (1 ≦ i < j ≦ N), such that j - i ≧ K and |P_i - P_j| = 1. Then, swap the values of P_i and P_j.



Among all permutations that can be obtained by applying this operation to the given permutation, find the lexicographically smallest one.

Constraints

* 2≦N≦500,000
* 1≦K≦N-1
* P is a permutation of the set {1, 2, ..., N}.

Input

The input is given from Standard Input in the following format:


N K
P_1 P_2 ... P_N


Output

Print the lexicographically smallest permutation that can be obtained.

Examples

Input

4 2
4 2 3 1


Output

2
1
4
3


Input

5 1
5 4 3 2 1


Output

1
2
3
4
5


Input

8 3
4 5 7 8 3 1 2 6


Output

1
2
6
7
5
3
4
8
NK=input()
NK="".join(NK).rstrip("\n").split(" ")
N,K,ans=int(NK[0]),int(NK[1]),[]
DP=[0 for s in range(N+1)]#各数字があるかどうか[数字],取りだせるのがindex
lis=input()
lis = "".join(lis).split(" ")
lis=[int(s) for s in lis]
print(lis)
St=0
for s in range(N):
	DP[lis[s]]=s+1
	#if DP[lis[s]]!=0:
		#DP[lis[s]]+=[s+1]#同じ数字が複数個ある場合の処理
def search(num):
	#if DP[num] 複数ある場合の処理
	comp=DP[num]#先頭が4の場合はここで3を探す
	if comp<DP[num+1]:
		return 0
	return comp#なかった場合は初期値の0を返す

def sort(START):
	global St
	compare=START #この場合はlis[0]がSTART?
	comp=search(compare-1)
	start=DP[START]
	if (comp==0): #& (start==1):
		#DP[lis[0]]=0
		#ans.append(lis.pop(0))#先頭がこれ以上小さくなることはないので取り出す
		#for s in range(len(DP)):
			#if DP[s]==0:
				#continue
			#DP[s]-=1
		St+=1
		return
	#print(str(comp)+" "+str(start))
	if (comp-start)<K:
		#print("<K")
		sort(lis[comp-1])
		return
	if (comp-start)>=K :
		#print(">=K")
		temp=DP[lis[start-1]]
		DP[lis[start-1]]=comp
		DP[lis[comp-1]]=temp
		temp=lis[start-1]
		lis[start-1]=lis[comp-1]
		lis[comp-1]=temp
#elif compが複数だった場合の処理
#elif 存在するが距離がK以下の場合の処理　そこからK以上のものだけを探せばいい。証明済み
d=0

while St!=N-1:
	sort(lis[St])
	#print(DP)
	print(lis)
	#print(ans)
	#d+=1
	#if d==20:
		#break

#print(ans)
for s in range(len(lis)):
	print(lis[s])
