//We assume that initially FileA contains one number per line.
//The last number is a dummy and it is ignored in sorting.
//The program uses FileB temporarily for sorting.
//Final result is always in FileA.


import javabook.*;
import java.io.*;

class MergeSort
{   

    public static void main(String[] args) throws IOException
    {
     sort();
    } 


    public static void sort() throws IOException
    {int N=0,L,a,l,k,j,i,s,p;
     String str;
     double a1,a2;

     FileReader fileReaderA2 =  null;
     BufferedReader brA2 = null;
     FileReader fileReaderB1 =  null;
     BufferedReader brB1 = null;
     FileReader fileReaderB2 =  null;
     BufferedReader brB2 = null;
     FileOutputStream fileOutStreamA = null;
     PrintWriter pwA = null;
     FileOutputStream fileOutStreamB = null;
     PrintWriter pwB = null;
     File datFileA = new File("FileA");
     File datFileB = new File("FileB");

     FileReader fileReaderA1 = new  FileReader(datFileA);
     BufferedReader brA1 = new  BufferedReader(fileReaderA1);
     str = brA1.readLine(); 
     while(str != null) {N++; str = brA1.readLine();}
     N--;
     brA1.close();
     fileReaderA1.close(); 

     int m = (int)(Math.log(N)/Math.log(2));
     if (Math.pow(2,m+1) < N) m++;
     boolean atob = true;
     for(s=0; s<=m; s++)
        {
         L=(int) Math.pow(2,s+1);
         a = N/L;
         i=0;j=L/2;l=0;

//In the beginning of each pass each segment of length L/2 is sorted
// and after this pass each segment of length L will be sorted.
// atob = true means that the result of the previous pass is in FileA
// and the result of this pass will be written in FileB. Reverse
// will be the case when  atob is false.

         if (atob)
           {
            fileReaderA1 = new  FileReader(datFileA);
            brA1 = new  BufferedReader(fileReaderA1);
            fileReaderA2 = new  FileReader(datFileA);
            brA2 = new  BufferedReader(fileReaderA2);
            fileOutStreamB = new  FileOutputStream(datFileB);
            pwB = new  PrintWriter(fileOutStreamB);

            str = brA1.readLine();
            a1 = (double) Convert.toDouble(str); 
            for (p=0;p<L/2;p++)  str = brA2.readLine();
            str = brA2.readLine();
            a2 = (double) Convert.toDouble(str);

// In each pass we will merge next two L/2 length segments


            for(k=1;k<=a;k++)
               {i=(k-1)*L; j = i+L/2;
                while ((i < (k-1)*L+L/2)&&(j < k*L))
                   {
                    if (a1 < a2) {pwB.println(a1);i++;
                                  str = brA1.readLine();
                                  a1 = (double) Convert.toDouble(str);
                                 }
                    else {pwB.println(a2);j++;
                          str = brA2.readLine();
                          a2 = (double) Convert.toDouble(str);
                         }
                    l++;
                   }
                if (i==(k-1)*L+L/2)while(j < k*L)
                                   {
                                    pwB.println(a2);  
                                    str = brA2.readLine();
                                    a2 = (double) Convert.toDouble(str);
                                    j++;l++;
                                   }
                else while (i < (k-1)*L+L/2)
                     {
                      pwB.println(a1); 
                      str = brA1.readLine();
                      a1 = (double) Convert.toDouble(str);
                      i++;l++;
                     }
                         for (p=0;p<L/2;p++)  str = brA1.readLine();
                         a1 = (double) Convert.toDouble(str);
                         if (k<a){
                                  for (p=0;p<L/2;p++)  str = brA2.readLine();
                                  a2 = (double) Convert.toDouble(str);
                                 }
               }

//After sorting integral number of L-segments, now 
// we deal with the remaining part.

            if (((a>0)&&(N-a*L > L/2))||(a==0))
               {i=a*L;j=i+L/2;
                if(a>0) {for (p=0;p<L/2;p++)  str = brA2.readLine();
                         a2 = (double) Convert.toDouble(str);
                        }
                while ((i < a*L+L/2)&&(j < N))
                   {
                    if (a1 < a2) {pwB.println(a1);i++;
                                  str = brA1.readLine();
                                  a1 = (double) Convert.toDouble(str);
                                 }
                    else {pwB.println(a2);j++;
                          str = brA2.readLine();
                          a2 = (double) Convert.toDouble(str);
                         }
                    l++;
                   }
                if (i==a*L+L/2)while(j < N)
                               {
                                pwB.println(a2);  
                                str = brA2.readLine();
                                a2 = (double) Convert.toDouble(str);
                                j++;l++;
                               }
                else while (i < a*L+L/2)
                     {
                      pwB.println(a1); 
                      str = brA1.readLine();
                      a1 = (double) Convert.toDouble(str);
                      i++;l++;
                     }
               }             
            else {j=a*L; 
                  while(j<N)
                  {
                   pwB.println(a2); 
                   str = brA2.readLine();
                   a2 = (double) Convert.toDouble(str);
                   j++;l++;
                  }

                 }
            pwB.println(a2);   //to print the dummy N+1st number
            brA1.close();
            fileReaderA1.close(); 
            brA2.close();
            fileReaderA2.close(); 
            pwB.close();
            fileOutStreamB.close();
            atob = false;
           }

// In the following segment  atob = false so data move from 
// FileB to FileA So this part is same as above except A <--> B.
         else
           {
            fileReaderB1 = new  FileReader(datFileB);
            brB1 = new  BufferedReader(fileReaderB1);
            fileReaderB2 = new  FileReader(datFileB);
            brB2 = new  BufferedReader(fileReaderB2);
            fileOutStreamA = new  FileOutputStream(datFileA);
            pwA = new  PrintWriter(fileOutStreamA);

            str = brB1.readLine();
            a1 = (double) Convert.toDouble(str); 
            for (i=0;i<L/2;i++)  str = brB2.readLine();
            str = brB2.readLine();
            a2 = (double) Convert.toDouble(str);

            for(k=1;k<=a;k++)
               {i=(k-1)*L; j = i+L/2;
                while ((i < (k-1)*L+L/2)&&(j < k*L))
                   {
                    if (a1 < a2) {pwA.println(a1);i++;
                                  str = brB1.readLine();
                                  a1 = (double) Convert.toDouble(str);
                                 }
                    else {pwA.println(a2);j++;
                          str = brB2.readLine();
                          a2 = (double) Convert.toDouble(str);
                         }
                    l++;
                   }
                if (i==(k-1)*L+L/2)while(j < k*L)
                                   {
                                    pwA.println(a2);  
                                    str = brB2.readLine();
                                    a2 = (double) Convert.toDouble(str);
                                    j++;l++;
                                   }
                else while (i < (k-1)*L+L/2)
                     {
                      pwA.println(a1); 
                      str = brB1.readLine();
                      a1 = (double) Convert.toDouble(str);
                      i++;l++;
                     }
                         for (p=0;p<L/2;p++)  str = brB1.readLine();
                         a1 = (double) Convert.toDouble(str);
                         if (k<a){
                                  for (p=0;p<L/2;p++)  str = brB2.readLine();
                                  a2 = (double) Convert.toDouble(str);
                                 }
               }
            if (((a>0)&&(N-a*L > L/2))||(a==0))
               {i=a*L;j=i+L/2;
                if (a>0) {for (p=0;p<L/2;p++)  str = brB2.readLine();
                          a2 = (double) Convert.toDouble(str);
                         }
                while ((i < a*L+L/2)&&(j < N))
                   {
                    if (a1 < a2) {pwA.println(a1);i++;
                                  str = brB1.readLine();
                                  a1 = (double) Convert.toDouble(str);
                                 }
                    else {pwA.println(a2);j++;
                          str = brB2.readLine();
                          a2 = (double) Convert.toDouble(str);
                         }
                    l++;
                   }
                if (i==a*L+L/2)while(j < N)
                               {
                                pwA.println(a2);  
                                str = brB2.readLine();
                                a2 = (double) Convert.toDouble(str);
                                j++;l++;
                               }
                else while (i < a*L+L/2)
                     {
                      pwA.println(a1); 
                      str = brB1.readLine();
                      a1 = (double) Convert.toDouble(str);
                      i++;l++;
                     }
               }             
            else {j=a*L; 
                  while(j<N)
                  {
                   pwA.println(a2); 
                   str = brB2.readLine();
                   a2 = (double) Convert.toDouble(str);
                   j++;l++;
                  }

                 }
            pwA.println(a2);   //to print the dummy N+1st number
            brB1.close();
            fileReaderB1.close(); 
            brB2.close();
            fileReaderB2.close(); 
            pwA.close();
            fileOutStreamA.close();
            atob = true;
           }
        }
//In case the final result is created in FileB
// then we transfer it in FileA

     if (((N>Math.pow(2,m-1))&&!atob)||((N==Math.pow(2,m-1))&&atob))
        {
         fileReaderB1 = new  FileReader(datFileB);
         brB1 = new  BufferedReader(fileReaderB1);
         fileOutStreamA = new  FileOutputStream(datFileA);
         pwA = new  PrintWriter(fileOutStreamA); 
         for(k=0;k<=N;k++) 
           {
            str = brB1.readLine();
            a1 = (double) Convert.toDouble(str);
            pwA.println(a1);
           }
         brB1.close() ;
         fileReaderB1.close();
         pwA.close(); 
         fileOutStreamA.close();
         System.exit(0);
       }
    }

}