Chef has an array of N numbers and a magic function which can swap two array values if their distance is strictly greater than K units. Since his friend Pishty is obsessed with sorted array, Chef wants to make the lexicographically minimum array possible by using this magic function. He can use this magic function any number of times. Help him find the solution.

Distance: absolute difference of indices
Lexicographically minimum: Given two arrays P_{1},P_{2}….P_{r} and Q_{1},Q_{2}….Q_{r} of same length the first one is smaller than the second one for the lexicographical order, if P_{i}  < Q_{i} for the first i where P_{i} and Q_{i} differ. 

------ Input ------ 

First line of input contains two space separated integers N and K
Next line contains N space separated integers A_{1}, A_{2}, ..., A_{N} denoting chef's array.

------ Output ------ 

The only line of output contains N space separated integers denoting the lexicographically minimum array possible after all such possible swap operations.

------ Constraints ------ 

$1 ≤ N,K ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
 
----- Sample Input 1 ------ 
6 2
4 6 3 2 5 1
----- Sample Output 1 ------ 
1 2 3 4 5 6
----- explanation 1 ------ 
In the first operation, Chef can use his magic function to swap 2 and 4 since their distance = 3 (greater than 2). New array formed: 2 6 3 4 5 1Similarly, he can now swap 2 and 1 to obtain: 1 6 3 4 5 2Finally he can swap 2 and 6 to obain: 1 2 3 4 5 6.This is the lexicographically minimum array possible.

Difficulty: MEDIUM_HARD
Tags: Sorting
Skill types: Sorting

Starter code:

Solutions:
from sys import stdin
input = stdin.readline
(n, k) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
if k < n // 2:
	print(*sorted(a))
	exit()
l = n - k - 1
r = n - (n - k - 1)
rem = []
for i in range(n - k - 1):
	rem.append(a[i])
for i in range(r, n):
	rem.append(a[i])
rem.sort()
ans = []
j = 0
for i in range(n):
	if i < l or i >= r:
		ans.append(rem[j])
		j += 1
	else:
		ans.append(a[i])
print(*ans)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
l = -1
r = -1
if k >= n - 1:
	for i in range(n):
		print(a[i], end=' ')
	print()
elif k >= n // 2:
	r = k
	l = n - k - 1
	al = []
	al = a[:l] + a[r + 1:]
	am = a[l:r + 1]
	al.sort()
	for i in range(l):
		print(al[i], end=' ')
	for i in range(r - l + 1):
		print(am[i], end=' ')
	for i in range(l, len(al)):
		print(al[i], end=' ')
	print()
else:
	a.sort()
	for i in range(n):
		print(a[i], end=' ')
	print()


(n, k) = map(int, input().split())
l = list(map(int, input().split()))
l1 = []
can_swap = [0] * n
for i in range(n):
	if i + k < n - 1 or i - k > 0:
		can_swap[i] = 1
		l1.append(l[i])
l1.sort()
x = 0
for i in range(n):
	if can_swap[i] == 1:
		l[i] = l1[x]
		x += 1
print(*l)


import math
(a, b) = map(int, input().split())
c = list(map(int, input().split()))
d = []
for i in range(a):
	if i + b + 1 < a:
		d.append(c[i])
		d.append(c[i + b + 1])
		c[i] = -1
		c[i + b + 1] = -1
d.sort()
x = 0
for i in range(a):
	if c[i] == -1:
		c[i] = d[x]
		x += 1
print(*c)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
if k < n // 2:
	a = sorted(a)
	for x in a:
		print(x, end=' ')
elif k < n:
	temp = a[:n - k - 1] + a[k + 1:]
	temp = sorted(temp)
	for i in range(n - k - 1):
		print(temp[i], end=' ')
	i += 1
	for j in range(n - k - 1, k + 1):
		print(a[j], end=' ')
	for j in range(k + 1, n):
		print(temp[i], end=' ')
		i += 1
else:
	for x in a:
		print(x, end=' ')


(N, K) = map(int, input().split())
L = list(map(int, input().split()))
B = [i for i in L]
for i in range(N):
	if i + K + 1 < N:
		B[i] = -1
		B[i + K + 1] = -1
	else:
		break
vals = []
for i in range(N):
	if B[i] == -1:
		vals.append(L[i])
vals.sort()
j = 0
for i in range(N):
	if B[i] == -1:
		B[i] = vals[j]
		j += 1
print(*B)


def ii():
	return int(input())

def mi():
	return map(int, input().split())

def li():
	return list(mi())
(N, K) = mi()
K += 1
A = li()
B = []
for i in range(N):
	if i - K >= 0 or i + K < N:
		B.append(A[i])
B.sort(reverse=True)
for i in range(N):
	if i - K >= 0 or i + K < N:
		A[i] = B.pop()
print(*A)


(N, K) = map(int, input().split())
l = list(map(int, input().split()))
l1 = []
can_swap = [0] * N
for i in range(N):
	if i + K < N - 1 or i - K > 0:
		can_swap[i] = 1
		l1.append(l[i])
l1.sort()
x = 0
for i in range(N):
	if can_swap[i]:
		l[i] = l1[x]
		x += 1
print(*l)