/ Marrah McClelland

import java.util.*;
import java.io.*;
import java.lang.Math.*;

//I apologize for not printing the count at the end I didn't know
//how to make c a global variable in java.
//The array also needs to be set to a global value.  My return statements
//don't work because they get called multiple times. The MergeSort
function
//does work on it's own though. It just doesn't return the right array.
//The running time of this function should be n log n since I used
//MergeSort to sort the list before printing.
//

class Readints{

public static int[] mergeSort(int a[], int start, int segLength, int c) {

    int half = segLength / 2;     
    
    if ( half > 1 )
      mergeSort (a, start, half, c);
    if ( segLength - half > 1 )
      mergeSort (a, start + half, segLength - half, c);
    
     int t1[] = new int[half];
     int t2[] = new int[segLength - half];
     int i = start;
     for ( int j = 0; j < half; ){
       t1[j++] = a[i++]; c++;}
     for ( int j = 0; j < segLength - half; ){
       t2[j++] = a[i++]; c++;}

     System.out.println("count = " + c);

    return( merge (a, start, t1, t2, c));
  }

public static int [] merge (int a[], int start, int t1[], int t2[], int c)
{
    int index = start;
    int t1index = 0;
    int t2index = 0;

    while ( t1index < t1.length && t2index < t2.length ) {

        if ( t1[t1index] <= t2[t2index] )
          {  a[index] = t1[t1index++]; c++;}
        else
        {  a[index] = t2[t2index++]; c++;}

    }
    while ( t1index < t1.length ) {

      a[index] = t1[t1index++];
      c++;
    }
    while ( t2index < t2.length ) {

        a[index] = t2[t2index++];
        c++;

    }
    return a;
  }
  
public static void main (String[] args) throws IOException{
        int k = 0;
        int c = 0;      
        int[] array = new int[5000];

        Random r = new Random();

        for(int j = 0; j < 5000; j++)
          array[j] = (int)(Math.random()*5000); 

        array = mergeSort(array, 0, 5000, c);

        InputStream in = System.in;
        StreamTokenizer num = new StreamTokenizer(in);
        if (num.nextToken() == StreamTokenizer.TT_NUMBER)
          k = (int)num.nval;

        int i = 0;

          while ( i < 4999){
            if ((i+1)%k == 0){
              System.out.println("\nQuantile =" + array[i]);
              i++;}  

            System.out.print(array[i]);
            System.out.print("  ");

            i++;
          }
          
        System.out.println ("\nk=" + k);

        }//end main
}//end Readints