#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;

int n,m,p[N];
string s[N];
vector<int> sta[N];

vector<int> exkmp(string s){
	int n=s.size()-1;
	vector<int> z(n+1,0);
	for(int i=2,l=1,r=1;i<=n;i++){
		if(i<=r&&z[i-l+1]<r-i+1)z[i]=z[i-l+1];
		else{
			z[i]=max(0,r-i+1);
			while(i+z[i]<=n&&s[i+z[i]]==s[z[i]+1])z[i]++;
		}
		if(i+z[i]-1>r)l=i,r=i+z[i]-1;
	}
	return z;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++)cin>>s[i],s[i]=" "+s[i];
	int min_len=2*(s[1].size()-1)-n;
	for(int i=1;i<=m;i++){
		vector<int> z=exkmp(s[i]);
		vector<int> &v=sta[i];
		// cout<<i<<" "<<s[i].size()<<endl;
		for(int j=2;j<s[i].size();j++){
			// cout<<i<<" "<<s[i].size()<<" "<<j<<endl;
			int len=s[i].size()-j;
			if(len<min_len)break;
			if(z[j]!=len)continue;
			v.emplace_back(len);
		}
		// for(auto x:v)cout<<x<<" ";cout<<endl;
	}

	iota(p+1,p+m+1,1);
	sort(p+1,p+m+1,[&](int x,int y){
		return make_pair(sta[x],x)<make_pair(sta[y],y);
	});
	for(int i=1;i<=m;i++)cout<<s[p[i]].substr(1)<<endl;
	return 0;
}