import java.util.* ;
import java.text.* ;

class Sort {
  /* Un « Collator » possède une méthode « compare » qui tient compte
     des particularités de la langue française dans les comparaisons
     de mots (ie e < é < è < ê < f) */
  private static final Collator col = Collator.getInstance() ;
  /* Coquetterie, récupérer le séparateur de ligne de façon portable */
  private static final String nl = System.getProperty("line.separator") ;
  /* Un « Comparator » est un objet qui possède une méthode
     compare utilisable pour le tri des Collections.
     Ici nous définisssons la comparaison dont nous avons besoin
      1. D'abord par ordre décroissant du nombre d'occurrences
      2. Ensuite ordre des mots français */
  private static final
    Comparator <Map.Entry<String,Integer>> comparator =
    new Comparator <Map.Entry<String,Integer>> () {
        public int compare
          (Map.Entry<String,Integer> e1, Map.Entry<String,Integer> e2) {
          int c1 = e1.getValue() ;
          int c2 = e2.getValue() ;
          if (c1 < c2) return 1 ;
          else if (c1 > c2) return -1 ;
          else return col.compare(e1.getKey(), e2.getKey()) ;
        }
    } ;

  /* Trier puis changer en String la List de Map.Entry donnée en argument
     Un Map.Entry<K,V> est tout simplement une paire d'objets <k,v>
     on récupère k par e.getKey() et v par e.getValue() */
  static String toString(List<Map.Entry<String,Integer>> list) {
    /* Trier, tri impératif list contiendra la listes triée */
    Collections.sort (list, comparator) ;
    /* Changer en String */
    StringBuilder r = new StringBuilder () ;
    /* Boucle spéciale sur les elts de type E d'un List<E> */
    for (Map.Entry<String,Integer> e : list) {
      r.append(e.getKey() + ": " + e.getValue() + nl) ;
    }
    return r.toString() ;
  }
}