ebal

#include <bits/stdc++.h>

#define itn int

using namespace std;

void msd(vector<string>& a, int l, int r, int d = 0){
    if (r-1-l <= 0)
        return;
    vector<vector<int> > indices(256);
    for (int i = l; i < r; i++){
        if (d < a[i].length())
            indices[a[i][d]].push_back(i);
        else
            indices[0].push_back(i);
    }
    vector<int> place;
    vector<int> initialIndex;
    for (int i = l; i < r; ++i){
        place.push_back(i);
        initialIndex.push_back(i);
    }
    int cntSwap = 0;
    for (int i = 0; i < 256; ++i){
        for (int j = 0; j < indices[i].size(); ++j){
            a[cntSwap+l].swap(a[place[indices[i][j] - l]]);
            swap(initialIndex[cntSwap], initialIndex[place[indices[i][j]-l]-l]);
            swap(place[indices[i][j]-l], place[initialIndex[place[indices[i][j]-l]-l]-l]);
            cntSwap++;
        }
        if (i != 0)
            msd(a, cntSwap - indices[i].size() + l, cntSwap + l, d+1);
    }
}

int main(){
    string s;
    vector<string> a;
    while (getline(cin, s)){
        a.push_back(s);
    }
    int n = a.size();
    msd(a, 0, n);

    for (int i = 0; i < n; ++i)
        cout << a[i] << endl;

    return 0;
}