/*
 * This code is from "Algorithms in C, Third Edition,"
 * by Robert Sedgewick, Addison Wesley Longman, 1998.
 */

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

#define exch(A, B) { int t = A; A = B; B = t; } 
#define compexch(A, B) if ((B)<(A)) exch(A, B)

#define M 100000

#define bitsword    32
#define digitsword  (bitsword/bitsdigit)

#define bitsdigit    2
#define R            (1<<bitsdigit)

#define digit(A,B) (((A) >> (bitsword-((B)+1)*bitsdigit)) & (R-1))

void insertion(int a[], int l, int r)
  { int i;
    for (i = l+1; i <= r; i++) compexch(a[l], a[i]);
    for (i = l+2; i <= r; i++)
      { int j = i; int v = a[i]; 
        while (v<a[j-1])
          { a[j] = a[j-1]; j--; }
        a[j] = v; 
      } 
  }

#define cutoffN 1
#define maxN 10000000
int aux[maxN];

#define bin(A) l+count[A]
void radixMSD(int a[], int l, int r, int w)
  { int i, j, count[R+1]; 
    if (w > digitsword) return;
    if (r-l <= cutoffN) { insertion(a, l, r); return; }
    for (j = 0; j < R; j++) count[j] = 0;
    for (i = l; i <= r; i++) 
      count[digit(a[i], w) + 1]++;
    for (j = 1; j < R; j++) 
      count[j] += count[j-1];
    for (i = l; i <= r; i++) 
      aux[l+count[digit(a[i], w)]++] = a[i];
    for (i = l; i <= r; i++) a[i] = aux[i];
    radixMSD(a, l, bin(0)-1, w+1);
    for (j = 0; j < R-1; j++)
      radixMSD(a, bin(j), bin(j+1)-1, w+1);
  }

int main(int argc, char *argv[])
  { int i, N = atoi(argv[1]), sw = atoi(argv[2]);
    int *a = malloc(N*sizeof(int));
    if (sw) 
      for (i = 0; i < N; i++) 
        a[i] = M*(1.0*rand()/0x80000000);
    else {
      N=0;
      while (scanf("%d", &a[N]) == 1) N++;
    }
    radixMSD(a, 0, N-1, 0);
    for (i = 0; i < N; i++) printf("%3d ", a[i]);
    printf("\n");
    return 0;
  }