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 NewRadixSortStrings
{
  // +----------+------------------------------------------------
  // | Strategy |
  // +----------+
/*
  Put each string into a "bucket" based on a character at a particular
    position.
  Join all those buckets back together
  Resort based on the previous 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) {
    // Set up the result vector.
    Vector result = (Vector) stuff.clone();

    // Set up the buckets.
    Vector[] buckets = new Vector[NUMCHARS];  
    for (int i = 0; i < NUMCHARS; i++) {
      buckets[i] = new Vector();
    }
    
    // Determine the number of strings.
    int numStrings = stuff.size();

    // Find the length of the longest string
    int len = 0;
    for (int i = 0; i < numStrings; i++) {
      String str = (String) result.get(i);
      if (str.length() > len) len = str.length();
    } // for

    // Step through the positions from right to left, shoving into
    // buckets and then reading out again
    for (int pos = len-1; pos >=0; pos--) {
      // Put each string into the appropriate bucket
      for (int i = 0; i < numStrings; i++) {
        String str = (String) result.get(i);
        int bucketnum;
        // If the string is too short, shove it at the beginning
        if (str.length() <= pos)
          bucketnum = 0;
        else
          bucketnum = str.charAt(pos);
        buckets[bucketnum].add(str);
      }
      // Read it back out again, clearing the buckets as we go.
      result.clear();
      for (int i = 0; i < NUMCHARS; i++) {
        result.addAll(buckets[i]);
        buckets[i].clear();
      } // for(i)
    } // for(pos)

    // That's it, we're done.
    return result;
  } // sort


  // +------+----------------------------------------------------
  // | 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) {
      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 NewRadixSortStrings