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;
typedef long long ll;
typedef long double ld;
const int MOD = (int)1e9 + 7;
const int MAXN = (int)5e5 + 3;
const int infint = (int)1e9 + 3;
const ll inf = (ll)2e18;
int n, k, p[MAXN], q[MAXN], oc[MAXN];
set <int> L, R;
vector <int> G[MAXN];
int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
	{
		cin >> p[i];
		q[p[i]] = i;
	}
	for (int i = 1; i < k; i++)
		R.insert(p[i]);
	for (int i = 1; i <= n; i++) 
	{
		if (i + k - 1 <= n)
			R.insert(p[i + k - 1]);
		if (i)
			R.erase(p[i - 1]);
		L.insert(p[i]);
		if (i > k)
			L.erase(p[i - k]);
		auto it = R.upper_bound(p[i]);
		if (it != R.end())
			G[i].push_back(q[*it]), oc[q[*it]]++;
		it = L.upper_bound(p[i]);
		if (it != L.end())
			G[i].push_back(q[*it]), ++ oc[q[*it]];
	}
	L.clear(); R.clear();
	for (int i = 1; i <= n; ++ i) 
		if (oc[i] == 0)
			L.insert(i);
	int tp = 0;
	while (L.size())
	{
		int pos = (*L.begin());
		p[++tp] = pos;
		L.erase(L.begin());
		for (int i = 0; i < G[pos].size(); ++ i)
		{
			int v = G[pos][i]; -- oc[v];
			if (oc[v] != 0)
				continue;
			L.insert(v);
		}
	}
	for (int i = 1; i <= n; ++ i)
		q[p[i]] = i;
	for (int i = 1; i <= n; ++ i)
		cout << q[i] << "\n";
}
