import java.awt.*;
import java.io.*;
/**
* Finding the k quantiles
*@author John A. Lawson III
*/

public class Ass1  {
/**
*the list of integers read
*/
 private static int[] theList;
/**
* The number of quantiles to find
*/
 private static int numOfQuantiles;
/**
* The number of comparisons made
*/ 
private static int comparisons=0;
/**
* A string read from input that is converted to intergers
*/
public static StringBuffer aReadString;
/**
* Reads integers from system input
* Then has them sorted then the quantiles are outputed 
*@param argv command line arguments (none used)
*@return nothing
*/
public static void main(String[] argv)  {
 theList = new int[5000]; 
 int unicode; //unicode value read
 int count=0; 
try {
  aReadString = new StringBuffer (); //String Buffer emptied
  while (count<5001) {
   unicode = System.in.read(); 
   if (((char) unicode=='-') && (aReadString.length()==0))
    aReadString.append((char) unicode); // - and empty buffer put - in buffer
   else if (Character.isDigit((char) unicode)) 
     aReadString.append((char) unicode); // digits go in buffer
   else {
    if (aReadString.length() != 0) { //Buffer not empty add number to list
     if (count<5000)
       theList[count]=Integer.parseInt(aReadString.toString());
     else
       numOfQuantiles=Integer.parseInt(aReadString.toString());
     count=count+1;
      aReadString = new StringBuffer (""); //empty the buffer
    }
   }
  } 
   qsort(0,4999); 
   for(int n=0;n<numOfQuantiles;n++) 
    System.out.println(theList[n*(5000/numOfQuantiles)]);
   System.out.println(comparisons);  
 }
 catch (IOException h)
 {
  System.out.println("There was an IOException "+h);
 }
}

private static void qsort (int lower, int upper)  {
int thePartition=partition(lower,upper);
if (lower<upper){
 comparisons++; 
 qsort(lower, thePartition);
  qsort(thePartition+1, upper);
 }
}
private static int partition(int lower, int upper) {
int temp; 
int temp2;
temp=(int) Math.random()*(upper-lower)+lower;
temp2=theList[lower];
theList[lower]=theList[temp];
theList[temp]=temp2;
return oPartition(lower, upper);
}

private static int oPartition(int lower, int upper) {
int temp1;
int temp2;
int temp3;
int temp4;
temp1=theList[lower];
temp2=lower;
temp3=upper;
while (true) {
while (theList[temp3]>temp1) {
comparisons++;
temp3=temp3-1;
}
comparisons++;
while(theList[temp2]<temp1) {
 comparisons++;
 temp2=temp2+1;
} 
comparisons++;
if (temp2<temp3) 
    {comparisons++;
     temp4=theList[temp2];
     theList[temp2]=theList[temp3];
     theList[temp3]=temp4;
    }
else {
  comparisons++; 
   return temp3;
  }
 }
 }
}