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;
const int N = 500010;
int p[N], mp[N];
int vis[N];
int stack[N], top;
int q[N], h, t;
int n, K;
int main() {
  int i, j;
  int x, now;
  scanf("%d%d", &n, &K);
  for (i = 1; i <= n; i++) scanf("%d", &p[i]);
  for (i = 1; i <= n; i++) mp[p[i]] = i;
  for (i = 1; i <= n; i++) {
    if (vis[p[i]]) continue;
    h = t = 0;
    top = 0;
    q[++t] = p[i];
    stack[++top] = i;
    now = i + K;
    for (j = p[i] - 1; j; j--) {
      if (vis[j]) break;
      x = mp[j];
      q[++t] = j;
      stack[++top] = x;
      if (x >= now) {
        h++;
        p[x] = q[h];
        mp[q[h]] = x;
        top--;
      } else
        now = max(now, x + K);
    }
    while (top) {
      vis[q[t]] = 1;
      p[stack[top]] = q[t];
      mp[q[t]] = stack[top];
      top--;
      t--;
    }
  }
  for (i = 1; i <= n; i++) printf("%d\n", p[i]);
  return 0;
}
