import java.io.*;

public class Quantiles {

    static int[] vals = new int[5000];  /// to hold input series
    static int[] quantiles; /// to hold quantiles
    static int n = 5000;    /// number of inputs
    static int d, k; /// d=n/k, k=quantiles
    static int cmpct;   /// comparison counter

    public static void main(String argv[]) throws IOException {

        /** Read from standard input one line at a time. Place each
            line into the array vals[] as an int.
        **/

        BufferedReader input = new BufferedReader(new
InputStreamReader(System.in));

        for (int r=0;r<n;r++) {
            vals[r] = Integer.parseInt(input.readLine());
        }

        /** Read k and store n/k.
        **/

        k = Integer.parseInt(input.readLine());
        d = n/k;

        /** Allocate a holding array for the quantiles we find so we can
            easily output them in order when done.
        **/
        quantiles = new int[k];

        /**
            Do the job.
        **/

        detSelect(0,n);

        /** Output the quantiles array and comparison count.
        **/

        for (int x=1;x<k;x++) System.out.println(quantiles[x]);
        System.out.println ("\ncomparisons: "+cmpct);

        /** Go home. Sleep.
        **/

    }


    public static void detSelect(int start, int fin) {

        /** If we are given an interval of length 1, return.
        **/

        if (start==fin) return;

        /** The return value from partition(s,f) will be the index in the
            interval for which we have determined the rank.
        **/

        int rank=partition(start,fin);

        /** Instead of passing each desired rank to detSelect explicitly,
            we will have each instance check to see in which partition of
            the current interval the desired quantiles lie, and perform
the
            appropriate subproblems. If the rank of the current partition
            pivot is a quantile, enter that value into the quantile array
            at index = quantile number.

            start/d + 1 is the number of the first quantile within this
            interval, unless vals[start] is a quantile, in which case
            start/d is an integer and is the number of the first
            quantile in the interval.
        **/

        /** Initially we assume there are no desired quantiles in this
            interval.
        **/

        boolean quantilesBelow=false;
        boolean quantilesAbove=false;

        for (int x=(start/d)*d==start?start/d:start/d+1;x*d<fin;x++) {
            if (x*d==rank) { quantiles[x]=vals[rank]; cmpct++; }
            else if (x*d<rank) { quantilesBelow = true; cmpct++; }
            else if (x*d>rank) { quantilesAbove = true; cmpct++; }
        }

        /** If we find that there are (ANY) desired quantile indexes
            in either partition around [rank], perform detSelect
            on the interval of that partition.
        **/

        if (quantilesBelow) detSelect(start,rank);
        if (quantilesAbove) detSelect(rank+1,fin);

        /** Otherwise, this iteration will close without doing anything,
            and other iterations will fill in the quantiles array.
        **/

        return;

    }


    public static int partition(int start, int fin) {

    /** In the partition function we will use the value located at
        the "middle" index of the interval. There is not expected
        to be a benefit from choosing that index, unless we are given
        already-sorted input.
    **/

        int hold;
        int x=vals[(fin+start)/2];
        int i=start;
        int j=fin-1;
        while (true) {
            while (vals[j]>x && j>start) { j--; cmpct++; }
            while (vals[i]<x && i<fin-1) { i++; cmpct++; }
            if (i<j) {
                hold=vals[i];
                vals[i]=vals[j];
                vals[j]=hold;
            }
            else return j;
        }
    }

}