import java.io.PrintWriter;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Vector;

/**
 * An attempt to sort strings using a variant of the Radix Sort method.
 */
public class RadixSortStrings
{
  // +----------+------------------------------------------------
  // | Strategy |
  // +----------+
/*
  Put each string into a "bucket" based on a character at a particular
    position.
  Resort those buckets based on the following positions.
  Join all the stuff back together again.
 */

  // +-----------+-----------------------------------------------
  // | Constants |
  // +-----------+

  /**
   * The number of characters (assume simple ASCII).
   */
  private static final int NUMCHARS = 128;


  // +----------------+------------------------------------------
  // | Public Methods |
  // +----------------+

  /**
   * Sort stuff (a vector of strings) alphabetically.
   */
  public static Vector sort(Vector stuff) {
    // Find the length of the longest string
    int len = 0;
    int numStrings = stuff.size();
    for (int i = 0; i < numStrings; i++) {
      String str = (String) stuff.get(i);
      if (str.length() > len) len = str.length();
    } // for
    // Go for it!
    return sort(stuff, 0, len-1);
  } // sort


  // +-----------------+-----------------------------------------
  // | Private Methods |
  // +-----------------+

  /**
   * Sort stuff based on the characters at positions start ... end.
   */
  private static Vector sort(Vector stuff, int start, int end) {
    // System.out.println("Positions " + start + " to " + end);
    if (start > end) return (Vector) stuff.clone();
    // The key to this method: Create buckets and shove in 'em.
    Vector[] buckets = new Vector[NUMCHARS];  
    for (int i = 0; i < NUMCHARS; i++) {
      buckets[i] = new Vector();
    }
    // Read through each string and put it in the right place.
    int numStrings = stuff.size();
    for (int i = 0; i < numStrings; i++) {
      String str = (String) stuff.get(i);
      int bucknum;
      if (str.length() <= start)
        bucknum = 0;
      else
        bucknum = str.charAt(start);
      buckets[bucknum].add(str);
    }
    // Sort each bucket on the remaining characters.
    for (int i = 0; i < NUMCHARS; i++) {
      if (buckets[i].size() > 0)
        buckets[i] = sort(buckets[i], start+1, end);
    }
    // Read stuff out of the vectors
    Vector result = new Vector();
    for (int i = 0; i < NUMCHARS; i++) {
      result.addAll(buckets[i]);
    }
    return result;
  } // sort(Vector, int, int)

  // +------+----------------------------------------------------
  // | Main |
  // +------+

  public static void main(String[] args)
    throws Exception
  {
    // Prepare input and output.
    BufferedReader keyboard = 
      new BufferedReader(new InputStreamReader(System.in));
    PrintWriter screen = new PrintWriter(System.out, true);

    // Build the vector
    Vector unsorted = new Vector();
    String str;
    while ( ((str = (keyboard.readLine())) != null) 
            && (!str.equals("")) ) {
      unsorted.add(str);
    } // while
    int veclen = unsorted.size();

    // Print out the unsorted vector
    screen.println("--------- UNSORTED ----------");
    for (int i = 0; i < veclen; i++) {
      screen.println(unsorted.get(i));
    }

    // Sort the vector
    Vector sorted = sort(unsorted);

    // Print out the sorted vector
    screen.println("---------- SORTED -----------");
    for (int i = 0; i < veclen; i++) {
      screen.println(sorted.get(i));
    }

  }//main
 
} // class RadixSortStrings