#include <string>
#include <list>
#include <iostream>

using namespace std;

template <typename T>
list<T> merge(const list<T> &l1, const list<T> &l2) {
	list<T> r;
	
	auto i1 = l1.begin(), i2 = l2.begin();

	while (true)
	{
		if (i1 == l1.end())
		{
			r.insert(r.end(), i2, l2.end());
			break;
		}
		
		if (i2 == l2.end())
		{
			r.insert(r.end(), i1, l1.end());
			break;
		}

		if (*i1 < *i2)
		{
			r.push_back(*i1);
			++i1;
		}
		else
		{
			r.push_back(*i2);
			++i2;
		}

	}
	return r;
}



int main()
{
	list<string> l;
	string s;

	for (;;) {
		cin >> s;

		if (s == "q") {
			break;
		}

		l.push_back(s);
	}

	list<list<string>> ll;

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

		l.pop_front();
	}

	while (ll.size() >= 2)
	{
		list<string> l1 = ll.front();
		ll.pop_front();
		list<string> l2 = ll.front();
		ll.pop_front();

		ll.push_back(merge(l1, l2));
	}

	if (!ll.empty())
	{
		l = ll.front();
		ll.pop_back();
	}

	for (auto i = l.begin(); i != l.end(); i++) {

		cout << *i << endl;
	}

    return 0;
}