/**********************************************
 ** Funny program - reads in words (terminated
 ** with a ; and prints the same words back
 ** again sorted by incresing length, with 
 ** ties broken by alphabetical order.
 **********************************************/
#include <iostream>
#include <string>
using namespace std;

/*****************************************
 ** struct def's and function prototypes
 *****************************************/
struct Node
{
  string data;
  Node *next;
};

void add2front(string val, Node* &L);
void printlist(Node* L);

// returns true if a should come before b and false otherwise
// i.e. it defines the order we'll use when sorting
bool before(string a, string b);

// If L is a list in sorted order (using comp to define order),
// insert adds val to the list in its proper place in the order.
void insertinorder(string val, Node* &L);

/*****************************************
 ** MAIN
 *****************************************/
int main()
{
  Node* L = 0;

  // Get strings and store (in order) in list!
  cout << "Enter words, terminated with a semi-colon :" << endl;
  string s;
  while(cin >> s && s != ";")
    insertinorder(s,L);

  // Print out list
  printlist(L);
  cout << endl;

  return 0;
}

/*****************************************
 ** Function definitions
 *****************************************/

bool before(string a, string b) 
{
  return a.length() == b.length() && a < b || a.length() < b.length();
}

void insertinorder(string val, Node* &L)
{
 if (L != 0 && before(L->data,val))
   insertinorder(val,L->next);
 else
   add2front(val,L);
}

void add2front(string val, Node* &L)
{
  Node *T = new Node;
  T->data = val;
  T->next = L;
  L = T;
}

void printlist(Node* L)
{
  if (L != 0)
  {
    cout << L->data << ' ';
    printlist(L->next);
  }
}