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
#include <bits/stdc++.h>

using namespace std;
#define X first
#define Y second
#define mid ((l+r)>>1)
#define lc k<<1,l,mid
#define rc k<<1|1,mid+1,r
#define pb push_back
typedef double db;
typedef long long ll;
typedef pair<int,int> P;
const int MAXN=5e5+10,INF=1<<28;
struct edge{int nxt,to;}e[MAXN<<2];
int head[MAXN],tot;
int n,k,in[MAXN],a[MAXN],pos[MAXN],seg[MAXN<<2];

void add_edge(int x,int y)
{e[++tot]=(edge){head[x],y};head[x]=tot;in[y]++;}
void Update(int pos,int val,int k,int l,int r)
{
	seg[k]=min(seg[k],val);
	if(l==r) return;//最后一层也要先更新再返回！ 
	if(pos<=mid) Update(pos,val,lc);
	else Update(pos,val,rc);
}
void Query(int &mn,int a,int b,int k,int l,int r)
{
	if(a<=l&&r<=b)
	{mn=min(mn,seg[k]);return;}
	if(a<=mid) Query(mn,a,b,lc);
	if(b>mid) Query(mn,a,b,rc);
}

int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) 
		scanf("%d",&a[i]),pos[a[i]]=i;
	for(int i=0;i<=4*n;i++) seg[i]=INF;
	for(int i=n;i>=1;i--)
	{
		int nxt=INF,pre=INF;
		//注意询问必须保证与[1,n]相交 
		Query(nxt,pos[i],pos[i]+k-1,1,1,n);
		Query(pre,pos[i]-k+1,pos[i],1,1,n);
		if(nxt!=INF) add_edge(pos[i],pos[nxt]);
		if(pre!=INF) add_edge(pos[i],pos[pre]);
		Update(pos[i],i,1,1,n);
	}
	
	priority_queue<int,vector<int>,greater<int> > q;
	for(int i=1;i<=n;i++)
		if(!in[i]) q.push(i);
	for(int i=1;i<=n;i++)
	{
		int t=q.top();q.pop();
		pos[i]=t;
		for(int j=head[t];j;j=e[j].nxt)
			if(!(--in[e[j].to])) q.push(e[j].to);
	}
	for(int i=1;i<=n;i++) a[pos[i]]=i;
	for(int i=1;i<=n;i++) printf("%d\n",a[i]);
	return 0;
}
/*
6 2
2 3 5 6 4 1 
*/