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>
#define f first
#define s second
#define MOD 1000000007
#define PMOD 998244353
#define pb(x) push_back(x)
using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> plii;
typedef pair<int, pii> piii;
const int INF = 1e9+10;
const ll LINF = 1LL*INF*INF;
const int MAXN = 5e5+10;
const int MAXM = 5e3+10;

priority_queue<int> pq;
vector<vector<int> > graph;
queue<int> que;

int A[MAXN];
int P[MAXN];
int res[MAXN];
int tmp[MAXN];
int mnv[MAXN];

void merge_sort(int st,int en,int k)
{
    if(st==en)return;

    int mid = (st+en)>>1;

    merge_sort(st,mid,k);
    merge_sort(mid+1,en,k);

    for(int i=st;i<=en;i++)tmp[i] = P[i];

    mnv[mid] = tmp[mid];

    for(int i=mid-1;i>=st;i--)
        mnv[i] = min(mnv[i+1],tmp[i]);

    int i = st,j = mid+1;
    int idx = st;

    while(i<=mid&&j<=en){
        if(mnv[i]<tmp[j]+k){
            P[idx] = tmp[i];
            idx++; i++;
        }
        else {
            P[idx] = tmp[j];
            idx++; j++;
        }
    }
    if(i<=mid){
        for(;i<=mid;i++)
            P[idx++] = tmp[i];
    }
    else {
        for(;j<=en;j++)
            P[idx++] = tmp[j];
    }

    return;
}

int main()
{
    int n,m,k,a,b,x,y,q;
    int sum = 0;
    int cnt = 0;
    int mx = 0;
    int mn = INF;
    int cur = 0, idx = -1;
    int tc;

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>n>>k;

    for(int i=1;i<=n;i++)
        cin>>A[i];

    for(int i=1;i<=n;i++)
        P[A[i]] = i;

    merge_sort(1,n,k);

    for(int i=1;i<=n;i++)
        res[P[i]] = i;

    for(int i=1;i<=n;i++)
        cout<<res[i]<<"\n";

    return 0;
}
