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

#define SIZE 5001
#define MIN_INDEX 1
#define MAX_INDEX 5000

/**
* Program: Finding Quantiles.
* Author: Jones Leung
* Date Created: February 5, 1999
* Rev. History: 
*/
int comparisons = 0;

/**
* Function prototypes
*/
void quicksort (int A[], int p, int r);
void swap (int A[], int i, int j);

/**
* Quicksort 
*/
void quicksort (int A[], int left, int right) {
	int i, last;
	
	/* stop recursion */
	if (left >= right) {  
		return;
	}

	/* move pivot to leftmost position */
	swap (A, left, (left + right) / 2);  
	
	last = left;

	/* partition */
	for (i = left + 1; i <= right; i++) {
		if (A[i] < A[left]) {
			swap (A, ++last, i);
		}
                comparisons++;
	}

	/* restore pivot */
	swap (A, left, last);

	/* recurse */
	quicksort (A, left, last - 1);
	quicksort (A, last + 1, right);
}

/**
* Swap two array elements
*/
void swap (int A[], int i, int j) {
	int temp;

	temp = A[i];
	A[i] = A[j];
	A[j] = temp;
}

main () {	
	int A[SIZE];
	int i = MIN_INDEX;

	/**
	* Initialize array with zeroes -- just in case.
	*/
	for (i = MIN_INDEX; i <= MAX_INDEX; i++) {
		A[i] = 0;
	}


	/**
	* Read MAX_INDEX distinct integer keys into array from standard input.
	*/
	for (i = MIN_INDEX; i <= MAX_INDEX; i++) {
		scanf ("%d\n", &A[i]);
	}

	/**
	* Read in the value of 'k' (The number of equal sized sets to partition the array into)
	*/
	int k = 0;
	scanf ("%d\n", &k);

	/**
	* Sort the array using quicksort O (n lg n) expected running time.
	*/
	quicksort (A, MIN_INDEX, MAX_INDEX);

	/**
	* Print kth quantiles on separate lines
	*/
	for (i = MIN_INDEX; i <= k - 1; i++) {							
		printf ("%d\n", A[i * MAX_INDEX / k]);				
	}

	/**
	* Print out value of 'k'
	*/
	printf ("k: %d\n", k);	

	/**
	* Print out number of comparisons
	*/
	printf ("Number of comparisons: %d\n", comparisons);
}