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;
using PII = pair<int, int>;
constexpr int maxn = 500000;
int P[maxn + 1], A[maxn + 1];
PII T[maxn << 2];
#define ls (v << 1)
#define rs (ls | 1)
#define tm ((tl + tr) >> 1)
void update(int v, int tl, int tr, int p, int x){
    if(tl == tr) T[v] = {x, p};
    else{
        if(p <= tm) update(ls, tl, tm, p, x);
        if(p > tm) update(rs, tm + 1, tr, p, x);
        T[v] = max(T[ls], T[rs]);
    }
}
PII get_max(int v, int tl, int tr, int L, int R){
    if(tl >= L and tr <= R) return T[v];
    PII res = {0, -1};
    if(L <= tm) res = max(res, get_max(ls, tl, tm, L, R));
    if(R > tm) res = max(res, get_max(rs, tm + 1, tr, L, R));
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N, K;
    cin >> N >> K;
    for(int i = 1; i <= N; i += 1){
        cin >> P[i];
        update(1, 1, N, i, P[i]);
    }
    priority_queue<int> q;
    auto add = [&](const int& i){
        if(i <= 0 || (i - 1) * K >= N) return;
        PII p = get_max(1, 1, N, (i - 1) * K + 1, i * K);
        if(p.first == 0) return;
        if(get_max(1, 1, N, p.second - K + 1, p.second + K - 1) != p) return;
        q.push(p.second);

    };
    for(int i = 1; i <= N; i += K) add((i + K - 1) / K);
    for(int i = N; i; i -= 1){
        while(A[q.top()]) q.pop();
        int p = q.top();
        A[p] = i;
        update(1, 1, N, p, 0);
        for(int j = -1; j <= 1; j += 1) add((p + K - 1) / K + j);
    }
    for(int i = 1; i <= N; i += 1) cout << A[i] << "\n";
    return 0;
}