///////////////////////////////////////////////////////////////////////////////
//	STUDENTS:
//
//	Alexei Medvedev (900-02-4663)
//	Yuriy Zhukovskiy (017-80-8728)
//	Liza Zvereva
//
//	DATE:		02/15/99
///////////////////////////////////////////////////////////////////////////////

#include <stdio.h>
#include <iostream.h>

int counter;                           // Global variable for counting comparisons

void main(void);

class Heap{
private:
	int *data;	               // array of integers
	int maxheapsize;               // its size
	int heapsize;	               // number of elements in it

	void FilterDown(int i);
	void FilterUp(int i);

public:
        Heap(int a[], int size){       // Constructor
           if (size <= 0)
              error("Bad list size.");
           data = a;
           maxheapsize=size;           // set heap's size
           heapsize=size;              // initial number of elements is size

           for (int i=(heapsize-1)/2; i>=0; i--)
      	      FilterDown(i);
	};

	void error(char errmsg[]){     // error handling
	   cerr << errmsg << "\n";
	   exit(1);                    // terminate the program
	};

	bool IsEmpty() const{	       // returns TRUE if the heap is empty
	   return (heapsize==0);
	};

	int Delete(){		       // Removing a pointer to a patient
	   if (heapsize==0)	       // Check if hep is empty
	      error("Heap empty");
	   int temp=data[0];	       // store the pointer
	   data[0]=data[heapsize-1];   // swap first and last element of an array
	   data[heapsize-1]=temp;
	   heapsize--;		       // Reduce the heap's size
	   FilterDown(0);	       // FilterDown the swapped element
	   return temp;		       // return a pointer to a removed patient
	};
};

void Heap::FilterDown (int i){         // Heap's FilterDown procedure
	int currentpos=i;
	int childpos=2*currentpos+1;
	int target=data[currentpos];
	while (childpos < heapsize){
	   if ((childpos+1 < heapsize) && (data[childpos+1] > data[childpos])){
	      childpos++;
	      counter++;
	   }
	   if (target >= data[childpos]){
	      counter ++;
	      break;
           }
	   else{
              counter ++;
	      data[currentpos]=data[childpos];
	      currentpos=childpos;
	      childpos=2*currentpos+1;
	   }
	}
	data[currentpos]=target;
};

void Heap::FilterUp (int i){           // Heap's FilterUp procedure
	int currentpos=i;
	int parentpos=(currentpos-1)/2;
	int target=data[currentpos];
	while (currentpos != 0 && (data[parentpos] < target)){
           counter++;
	   data[currentpos]=data[parentpos];
	   currentpos=parentpos;
	   parentpos=(currentpos-1)/2;
	}
	data[currentpos] = target;
};

void main(void) {
        counter=0;
        int n=5000;
        int a[n];
        int k = 1;
        for (int i=0; i<n; i++)
	   cin >> a[i];                // Get the input data
        cin >> k;                      // Get k 
        Heap b = Heap(a, n);           // Heapify
        for (int i=0; i<n; i++)        // Heapsort
           a[n-1-i]=b.Delete();
        for (int i=1; i <= k-1; i++)
	   cout << a[i*n/k] << "\n";   // Print the quantiles
        cout << counter << "\n";       // Print the number of comparisons
}