#include <stdio.h>
#include <stdlib.h>

void selectsort (long *a, long c, long d){
    long j, i, k, t;
    for (j=d; j>c; j--){
        for (i=j-1, k=j; i>=c; i--){
            if (a[i]>a[k]) k=i;
        }
        t = a[j];
        a[j] = a[k];
        a[k] = t;
    }
}


long partition (long *a, long c, long d){

    long i=c, j=d, ser, max, min,t, q=0;

    ser=(d-c-1)/2;
    if (ser>0){
        for (i=c, max=c; i<=d; i+=ser){
            if (a[i]>a[max])  max=i;
        }
        for (i=c, min=c; i<=d; i+=ser){
            if (a[i]<a[min])  min=i;
        }
        for (i=c; i<=d; i+=ser){
            if ((i!=max) && (i!=min))  q=i;
        }
    }
    else q=d;
    printf("%ld ", q);


    for (i=c, j=c; j<=d; j++){
        if (a[j]<a[q]){
            t = a[i];
            a[i] = a[j];
            a[j] = t;
            i++;
        }
    }

    t = a[i];
    a[i] = a[q];
    a[q] = t;

    return(i);

}

void quicksortrec(long* a, long nel, long c, long d, long m){

    long q;

    if ((c-d+1)<m) selectsort(a, c, d);
    else {
    if (c<d){
            q=partition(a, c, d);
            quicksortrec(a, nel, c, q-1, m);
            quicksortrec(a, nel, q+1, d, m);
    }

    }

}

void quicksort(long *a, long nel, long m){
    quicksortrec(a, nel, 0, nel-1, m);
}

int main(){

    long i, n, m;
    long *a;
        scanf("%ld", &n);
	scanf("%ld", &m);

	a = (long*)malloc(n * sizeof(long));
	for (i = 0; i < n; i++) scanf("%ld", a+i);

	quicksort(a, n, m);
	for (i = 0; i < n; i++) printf("%ld ", a[i]);
	free(a);

    return 0;
}