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<iostream>
#include<cstdio>
#include<queue>
using std::min;

const int MAXN=5e5+5,INF=~0U>>1;

int n,K;
int seq[MAXN],pos[MAXN];

const int rt=1;
struct SEGTN{int l,r,lc,rc;int mnv;} t[MAXN<<2];int tcnt=rt;
inline void upd(int o){t[o].mnv=min(t[t[o].lc].mnv,t[t[o].rc].mnv);}
void buildTree(int o,int l,int r)
{
	t[o].l=l,t[o].r=r;
	if(l==r) {t[o].mnv=INF;return;}
	int mid=(l+r)>>1;
	t[o].lc=++tcnt;buildTree(t[o].lc,l,mid);
	t[o].rc=++tcnt;buildTree(t[o].rc,mid+1,r);
	upd(o);
}
void ch(int o,int p,int v)
{
	if(t[o].l==t[o].r) {t[o].mnv=v;return;}
	int mid=(t[o].l+t[o].r)>>1;
	if(p<=mid) ch(t[o].lc,p,v);
	else ch(t[o].rc,p,v);
	upd(o);
}
int calMin(int o,int l,int r)
{
	if(l<=t[o].l&&t[o].r<=r) return t[o].mnv;
	int mid=(t[o].l+t[o].r)>>1;
	int res=INF;
	if(l<=mid) res=min(res,calMin(t[o].lc,l,r));
	if(r>mid) res=min(res,calMin(t[o].rc,l,r));
	return res;
}

int inDgr[MAXN];
struct E{int next,to;} e[MAXN<<1];int ecnt,G[MAXN];
void addEdge(int u,int v){e[++ecnt]=(E){G[u],v};G[u]=ecnt;inDgr[v]++;}

inline void buildGraph()
{
	buildTree(rt,1,n);
	int u,v;
	for(v=n;v;v--) 
	{
		u=calMin(rt,pos[v]-K+1,pos[v]);
		if(u<=n) addEdge(pos[u],pos[v]);
		u=calMin(rt,pos[v],pos[v]+K-1);
		if(u<=n) addEdge(pos[u],pos[v]);
		ch(rt,pos[v],v);
	}
}

std::priority_queue<int> heap;
inline void toposort()
{
	int i;
	for(i=1;i<=n;i++) if(!inDgr[i]) heap.push(i);
	for(int v=n;v;v--)
	{
		int u=pos[v]=heap.top();heap.pop();
		for(i=G[u];i;i=e[i].next)
			if(--inDgr[e[i].to]==0)
				heap.push(e[i].to);
	}
}

int main()
{
	int i;
	scanf("%d%d",&n,&K);
	for(i=1;i<=n;i++) scanf("%d",seq+i);
	for(i=1;i<=n;i++) pos[seq[i]]=i;
	buildGraph();
	toposort();
	for(i=1;i<=n;i++) seq[pos[i]]=i;
	for(i=1;i<=n;i++) printf("%d\n",seq[i]);
	return 0;
}