#include <iostream>
#include <vector>
#include <algorithm>

#define ll long long

using namespace std;

const int MOD1 = (int)1e9 + 7;
const int MOD2 = (int)1e9 + 9;

struct String {
    vector <int> matches;
    int ind, m, n;

    bool operator < (const String &other) const {
        int i = 0;
        for( ; i < matches.size() && i < other.matches.size() && matches[i] == other.matches[i]; i++);
        //cout << i << "\n";
        bool can_repeat = !(i == matches.size() || 2 * m - matches[i] > n);
        bool other_can_repeat = !(i == other.matches.size() || 2 * m - other.matches[i] > n);
        //cout << can_repeat << " " << other_can_repeat << " " << ind << " " << other.ind << "\n";
        if(!can_repeat) {
            if(!other_can_repeat)
                return ind < other.ind;
            return 1;
        }
        if(!other_can_repeat) return 0;
        //cout << ind << " " << other.ind << " " << (matches < other.matches) << "\n";
        return matches < other.matches || (matches == other.matches && ind < other.ind);
    }
} v[15];

int h1[1000005], h2[1000005], p1[1000005], p2[1000005];
string strs[15];

int get_hash_substr(int l, int r, int h[], int p[], int MOD) {
    return (h[r] - 1LL * h[l - 1] * p[r - l + 1] % MOD + MOD) % MOD;
}

void solve() {
    int n, s;
    cin >> n >> s;
    p1[0] = p2[0] = 1;
    for(int j = 1; j <= n; j++) {
        p1[j] = 31LL * p1[j - 1] % MOD1;
        p2[j] = 31LL * p2[j - 1] % MOD2;
    }
    for(int i = 1; i <= s; i++) {
        string str;
        cin >> str;
        str = '#' + str;
        int m = str.size() - 1;
        v[i].ind = i, v[i].m = m, v[i].n = n;

        for(int j = 1; j <= m; j++) {
            h1[j] = (31LL * h1[j - 1] + (str[j] - 'a' + 1)) % MOD1;
            h2[j] = (31LL * h2[j - 1] + (str[j] - 'a' + 1)) % MOD2;
        }
        for(int j = 1; j < m; j++) {
            if(get_hash_substr(1, j, h1, p1, MOD1) == get_hash_substr(m - j + 1, m, h1, p1, MOD1) && 
               get_hash_substr(1, j, h2, p2, MOD2) == get_hash_substr(m - j + 1, m, h2, p2, MOD2))
               v[i].matches.push_back(j);
        }
        reverse(v[i].matches.begin(), v[i].matches.end());
        //cout << "\n";
        strs[i] = str;
    }
    sort(v + 1, v + s + 1);
    for(int i = 1; i <= s; i++) {
        for(int j = 1; j <= v[i].m; j++)
            cout << strs[v[i].ind][j];
        cout << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    //cout << (vector<int>{1, 3} < vector<int>{2}) << "\n";
#ifdef LOCAL
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#else

#endif

    int T = 1;
    while(T--) {
        solve();
    }

    return 0;
}