/*
 * This code is from "Algorithms in C, Third Edition,"
 * by Robert Sedgewick, Addison Wesley Longman, 1998.
 * (With edits by Y. Kohayakawa)
 */

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

void comp_troque(int *A, int *B);
void insertion(int a[], int l, int r);

int main()
  { int i, N, sw;
    int *a;

    scanf("%d", &N);
    a = malloc(N*sizeof(int));

    scanf("%d", &sw);

    if (sw) 
      for (i = 0; i < N; i++) 
        a[i] = 1000*(1.0*rand()/RAND_MAX);
    else {
      N=0;
      while (scanf("%d", &a[N]) == 1) N++;
    }
    for (i = 0; i < N; i++) printf("%3d ", a[i]);
    printf("\n");

    insertion(a, 0, N-1);

    for (i = 0; i < N; i++) printf("%3d ", a[i]);
    printf("\n");
    return 0;
  }

void comp_troque(int *A, int *B)
{
  int t;
  if (*A > *B) 
    { t = *A; *A = *B; *B = t; } 
}

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