import java.util.* ;
import java.io.* ;

/*
  Expériences sur les tris de listes.
    java T1 => comparaison insertion/fusion -> 10000
    java T2 => essai de la fusion simple -> 10^6
    java -Xmx512M T3 => comparaison fusion itérative tri système
    java -Xmx512M T4 => comparaison fusion iterative en place, tri système 
 */

class List {
  int val ;     // L'élément
  List next ;   // La suite

  List (int  val, List next) {
    this.val = val ; this.next = next ;
  }

  List (int val) { this.val = val ; }

  static int card(List xs) {
    int r = 0 ;
    for ( ; xs != null ; xs = xs.next)
      r++ ; // pour r = r+1 ;
    return r ;
  }

  static String toString(List ps) {
    StringBuilder r = new StringBuilder () ; // Un StringBuilder à nous

    r.append("{") ;
    if (ps != null) {
      r.append(ps.val) ; // ajouter le premier entier
      ps = ps.next ;
      for ( ; ps != null ; ps = ps.next ) // et les suivants préfixés par ", "
        r.append(", " + ps.val) ;
    }
    r.append("}") ;

    // Renvoyer la chaîne contenue dans le StringBuilder
    return r.toString() ;
  }

  /*********************/
  /* Tri par insertion */
  /*********************/

  static List insertionSort(List xs) {
    List r = null ;
    for ( ; xs != null ; xs = xs.next )
      r = insert(xs.val, r) ;
    return r ;
  }

  private static boolean here(int x, List ys) {
    return ys == null || x <= ys.val ;
  }

  private static List insert(int x, List ys) {
    if (here(x, ys)) {
      return new List (x, ys) ;
    } else { // NB: !here(ys) => ys != null
      return new List (ys.val, insert(x, ys.next)) ;
    }
  }

  /********************************/
  /* Tri fusion, fusion récursive */
  /********************************/

  static List mergeSort(List xs) {
    List ys = null, zs = null ;
    boolean even = true ; // zéro est pair
    for (List p = xs ; p != null ; p = p.next ) {
      if (even) {
        ys = new List (p.val, ys) ;
      } else {
        zs = new List (p.val, zs) ;
      }
      even = !even ; // k+1 a la parité opposée à celle de k
    }
    if (zs == null) { // xs a zéro ou un élément
      return xs ; // et alors xs est triée
    } else { // Les longueurs de ys et sz sont < à la longueur de xs
      return merge(mergeSort(ys), mergeSort(zs)) ;
    }
  }

  static List merge(List xs, List ys) {
    if (xs == null) {
      return ys ;
    } else if (ys == null) {
      return xs ;
    } // NB: désormais xs != null && ys != null 
    else if (xs.val <= ys.val) {
      return new List (xs.val, merge(xs.next, ys)) ;
    } else { // NB: ys.val < xs.val
      return new List (ys.val, merge(xs, ys.next)) ;
    }
  }

  /********************************/
  /* Tri fusion, fusion itérative */
  /********************************/

  static List mergeIterSort(List xs) {
    List ys = null, zs = null ;
    boolean even = true ; // zéro est pair
    for (List p = xs ; p != null ; p = p.next ) {
      if (even) {
        ys = new List (p.val, ys) ;
      } else {
        zs = new List (p.val, zs) ;
      }
      even = !even ; // k+1 a la parité opposée à celle de k
    }
    if (zs == null) { // xs a zéro ou un élément
      return xs ; // et alors xs est triée
    } else { // Les longueurs de ys et sz sont < à la longueur de xs
      return mergeIter(mergeIterSort(ys), mergeIterSort(zs)) ;
    }
  }

  static List mergeIter(List xs, List ys) {
    if (xs == null) return ys ;
    if (ys == null) return xs ;

    /* Ici le resultat a une première cellule, reste à trouver ce qui va dedans */
    List r = null ;
    if (xs.val <= ys.val) {
      r = new List (xs.val) ; xs = xs.next ;
    } else {
      r = new List (ys.val) ; ys = ys.next ;
    }
    List last = r ; // Dernière cellule de la liste résultat

    /* Régime permanent */
    while (xs != null && ys != null) {
      if (xs.val <= ys.val) {
        last.next = new List (xs.val) ; xs = xs.next ;
      } else {
        last.next = new List (ys.val) ; ys = ys.next ;
      }
      last = last.next ; // Dernière cellule à nouveau
    }

    /* Ce n'est pas fini, une des deux listes peut ne pas être vide */
    if (xs == null) {
      last.next = ys ;
    } else {
      last.next = xs ;
    }
    return r ;
  }

  /*********************************/
  /* Tri fusion itératif, en place */
  /*********************************/

  static List mergeIterInPlaceSort(List xs) {
    if (xs == null || xs.next == null) return xs ;
    // Pour changer, une autre technique de division en 2

    List p = xs.next, q = xs ;
    do {
      p = p.next ;
      if (p == null) break ;
      q = q.next ;
      p = p.next ;
    } while (p != null) ;

    List ys = xs ;
    List zs = q.next ;
    q.next = null ;

    // Les longueurs de ys et sz sont < à la longueur de xs
    return
      mergeIterInPlace(mergeIterInPlaceSort(ys), mergeIterInPlaceSort(zs)) ;
  }

  static List mergeIterInPlace(List xs, List ys) {
    if (xs == null) return ys ;
    if (ys == null) return xs ;

    /* Ici le resultat a une première cellule, reste à trouver ce qui va dedans */
    List r = null ;
    if (xs.val <= ys.val) {
      r = xs ; xs = xs.next ;
    } else {
      r = ys ; ys = ys.next ;
    }
    List last = r ; // Dernière cellule de la liste résultat

    /* Régime permanent */
    while (xs != null && ys != null) {
      if (xs.val <= ys.val) {
        last.next = xs ; xs = xs.next ;
      } else {
        last.next = ys ; ys = ys.next ;
      }
      last = last.next ; // Dernière cellule à nouveau
    }

    /* Ce n'est pas fini, une des deux listes peut ne pas être vide */
    if (xs == null) {
      last.next = ys ;
    } else {
      last.next = xs ;
    }
    return r ;
  }

  /******************************/
  /* Tri bibliothèque, tableau  */
  /******************************/

  static List arraySort(List xs) {
    // Copier les eléments de xs dans un tableau t
    int sz = 0 ;
    for (List p = xs ; xs != null ; xs = xs.next) {
      sz++ ;
    }
    int [] t = new int[sz] ;
    int k = 0 ;
    for (List p = xs ; xs != null ; xs = xs.next, k++) {
      t[k] = xs.val ;
    }
    // Trier t
    Arrays.sort(t) ;
    // Fabriquer une liste avec les éléments de t
    List r = null ;
    for (k = sz-1 ; k >= 0 ; k--) {
      r = new List(t[k], r) ;
    }
    return r ;
  }

  static List gen(int n) {
    // Shuffle array
    Random rand = new Random (0) ;
    int t [] = new int[n] ;
    for (int k = 0 ; k < n ; k++) t[k] = k ;
    for (int k = 0 ; k < n ; k++) {
      int r = rand.nextInt(n-k) ;
      int x = t[k] ;
      t[k] = t[k+r] ;
      t[k+r] = x ;
    }
    // Build and return list
    List r = null ;
    for (int k = 0 ; k < n ; k++) {
      r = new List (t[k], r) ;
    }
    return r ;
  }
}

/*
  Réaliser les expériences.
  Héritage pour ne pas programmer mille fois la boucle de test.
 */
abstract class Tst {
  private PrintWriter out ;

  Tst(String name) {
    System.err.println("** " + name + " **") ;
    try {
      out = new PrintWriter(name) ;
    } catch (FileNotFoundException e) {
      System.err.println(e.getMessage()) ;
      System.exit(2) ;
    }
  }

  abstract List sort(List xs) ;

  void checkSorted(List xs, int n) { }

  void tst(int nsteps, int k) {    
    int n = 0 ;
    for(int i = 0 ; i < nsteps ; i++) {
      n += k ;
      List xs = List.gen(n) ;
      long start = System.nanoTime() ;
      List ys = sort(xs) ;
      long stop = System.nanoTime() ;
      checkSorted(ys, n) ;
      double t = (stop-start)/1000000000.0 ;
      String msg = n + " " + t ;
      out.println(msg) ; System.err.println(msg) ;
    }
    out.close() ;
  }
}

/*
  Première expérience comparaison Isertion/Fusion -> 10000
*/

class T1 {
  public static void main(String [] arg) {
    int nsteps = 20 ;
    int k = 250 ;
    if (arg.length > 0) nsteps = Integer.parseInt(arg[0]) ;
    if (arg.length > 1) k = Integer.parseInt(arg[1]) ;
    new Tst ("I") {
        List sort(List xs) { return List.insertionSort(xs) ; }
    }.tst(nsteps, k) ;
    new Tst ("M") {
        List sort(List xs) { return List.mergeSort(xs) ; }
    }.tst(nsteps, k) ;

  }
}

/*
  Expérience fusion simple
*/

class T2 {
  public static void main(String [] arg) {
    int nsteps = 100 ;
    int k = 10000 ;
    if (arg.length > 0) nsteps = Integer.parseInt(arg[0]) ;
    if (arg.length > 1) k = Integer.parseInt(arg[1]) ;
    new Tst ("M2") {
        List sort(List xs) { return List.mergeSort(xs) ; }
    }.tst(nsteps, k) ;
  }
}

/*
  Expérience fusion itérative 
*/
class T3 {
  public static void main(String [] arg) {
    int nsteps = 20 ;
    int k = 15000 ;
    if (arg.length > 0) nsteps = Integer.parseInt(arg[0]) ;
    if (arg.length > 1) k = Integer.parseInt(arg[1]) ;
    new Tst ("M") {
        List sort(List xs) { return List.mergeIterSort(xs) ; }
    }.tst(nsteps, k) ;
    new Tst ("A") {
        List sort(List xs) { return List.arraySort(xs) ; }
    }.tst(nsteps, k) ;
  }
}

/*
  Expérience fusion itérative en place
*/
class T4 {
  public static void main(String [] arg) {
    int nsteps = 20 ;
    int k = 100000 ;
    if (arg.length > 0) nsteps = Integer.parseInt(arg[0]) ;
    if (arg.length > 1) k = Integer.parseInt(arg[1]) ;
    new Tst ("M") {
      List sort(List xs) { return List.mergeIterInPlaceSort(xs) ; }
      void checkSorted(List xs, int n) {
        int k = 0 ;
        for ( ; xs != null ; xs = xs.next) {
          if (xs.val != k) throw new Error ("Not sorted") ;
          k++ ;
        }
        if (k != n) throw new Error ("Bad size") ;
      }
    }.tst(nsteps, k) ;
    new Tst ("A") {
        List sort(List xs) { return List.arraySort(xs) ; }
    }.tst(nsteps, k) ;
  }
}