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

int compare = 0, k, n = 5000, groupsize, extra, opt = 0;
int * quantilePos;
  

void  QuickSort(int a[], int left, int right)
{
  int i=0, j, tmp, pivot;
  if (++compare && right <= left) return;
  
  /* This is Optimization RST */
  /* It optimizes for large groupsize, but adds comparisons 
   * as currently counted) for small groupsize.
   */
  if (opt) {
    if (compare++ && extra <= 1) 
      i = left/(groupsize + 1);
    else 
      {
	int myleft = left, myextra = extra, one = 1;
	do {
	  i++;
	  myleft = myleft - groupsize -1 - one;
	  myextra--;
	} while (compare++ && extra>=1 && compare++ && myleft > 0);
	if (compare++ && myleft > 0) 
	  i += myleft/(groupsize + 1);
      }
    if (++compare && right<quantilePos[i]) 
      return;

  }
  /* end of optimization RST */


  pivot = a[right];
  i= left-1;
  j= right;
  for (;;) {
    while (++compare && a[++i]<pivot);
    while (++compare && a[--j]>pivot);
    if (++compare && i>=j) 
      break;
    
    tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
  }
    
  a[right] = a[i];
  a[i] = pivot;
  
  QuickSort(a, left, i-1);
  QuickSort(a, i+1, right);  
}



void algorithm(int k)
{
  int i=0, j, element, print = 0;
  
  quantilePos = calloc(k-1, sizeof(int));
  element = 0;
  groupsize = (n-k+1)/k;
  if (++compare && groupsize>=4) 
    opt = 1;
  printf("Groupsize is %d.\n", groupsize);
  extra = n - groupsize * k - k + 1;
  j=0;
  while (++compare && extra>1) {
    element = element + groupsize + 2;
    extra--;
    j++;
    quantilePos[i++] = element;
  }
  for (;++compare && j<k; j++) {
    element = element + groupsize + 1;
    quantilePos[i++] = element;
  }
}


int main(void)
{
  int a[5000], i; 

  for(i=0;i<n;i++) 
    scanf("%d",&a[i]);
  scanf("%d",&k);
 
  algorithm(k);
  QuickSort(a, 0, n-1);

  for (i = 0; i<k-1; i++)
    printf("%d\t", a[quantilePos[i]-1]);
  printf("\n");

  printf("Number of comparisons is:%d.\n", compare);  
return 0;
}