#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <list>
#include <set>

using namespace std;


/* mergesort, merge function */

list<string> merge(list<string> &list1, list<string> &list2) {
  list<string> result;
  /* iterate through the list until there is at least something in both */
  while (!list1.empty() && !list2.empty()) {
    if (list1.front() < list2.front()) {
      result.push_back(list1.front());
      list1.pop_front();
    } else {
      result.push_back(list2.front());
      list2.pop_front();
    }
  }

  /* consolidate the results */
  while (!list1.empty()) {
    result.push_back(list1.front());
    list1.pop_front();
  }

  while (!list2.empty()) {
    result.push_back(list2.front());
    list2.pop_front();
  }
  return result;
}

/*
 A sketch of the algorithm (iterated mergesort with a queue):
 [2,1,3,4] ::list<int>
 [[2], [1], [3], [4]]  :: list<list<int>>
 [[3],[4],[1,2]]
 [[1,2],[3,4]]
 [[1,2,3,4]]
*/

void mergesort(list<string> &l) {
  list<list<string>> ll; //we could also use an actual queue. :]

  while (!l.empty()) {
    list<string> tmp;
    tmp.push_back(l.front());
    ll.push_back(tmp);
    l.pop_front();
  }

  while(ll.size() > 1){
    auto temp1 = ll.front();
    ll.pop_front();
    auto temp2 = ll.front();
    ll.pop_front();
    ll.push_back(merge(temp1,temp2));
  }
  l = ll.front();
}



/* this mergesorts the words from the input */
int main() {
  std::list<string> lines;
  string line; //no matter they are called lines
  while(cin >> line) {
    lines.push_back(line);
  }

  mergesort(lines);

  for (const string &s: lines) {
    cout << s << endl;
  }
  
}


/* this writes only unique words from the input */
int main4() {
  /*multi*/set<string> words; //multisets are non-unique containers
  string word;
    while(cin >> word){
      words.insert(word);
  }

  for (const string &w: words) {
    cout << w;
    cout << "\n";
  }

  return 0;
}

/* this writes a histogram of letters on the input */
int main3() {
  string s;
  map<char, int> m;
  while(getline(cin, s)){ //getline returns the stream, which is convertible to bool, says whether the read has succeeded
    for (char c : s) {
      m[c]++;
    }
  }

  for (auto p : m) {
      cout << p.first;
      for (int i=0;i<p.second;i++)
        cout << "|";
      cout << endl;
  }

  return 0;
}

/* normal bubblesort with vectors */
int main2() {
  vector<float> x;
  vector<float>::value_type str;

  x.reserve(5); //this does not "create" any elements, the `x` is still semantically "empty" at this point

  for (size_t i = 0; i < 5; i++) {
    cin >> str;
    x.push_back(str);
  }

  for(size_t i = 0; i < x.size(); i++){
    for(size_t j = 0; j < x.size()-1; j++){
      if(x[j+1] < x[j]){
        std::swap(x[j],x[j+1]);
      }
    }
  }

  for(auto i = x.begin(); i!=x.end(); ++i) {
    cout << *i << endl;
  }

  return 0;
}