#include "bits/stdc++.h"
#include <random>
#include <chrono>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define SZ(x) ((lint)(x).size())
#define FOR(i, begin, end) for(lint i=(begin),i##_end_=(end);i<i##_end_;++i)
#define IFOR(i, begin, end) for(lint i=(end)-1,i##_begin_=(begin);i>=i##_begin_;--i)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define endk '\n'
using namespace std; typedef unsigned long long _ulong; typedef long long int lint; typedef long double ld; typedef pair<lint, lint> plint; typedef pair<ld, ld> pld;
struct fast_ios { fast_ios() { cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }; } fast_ios_;
template<class T> auto add = [](T a, T b) -> T { return a + b; };
template<class T> auto f_max = [](T a, T b) -> T { return max(a, b); };
template<class T> auto f_min = [](T a, T b) -> T { return min(a, b); };
template<class T> using V = vector<T>;
using Vl = V<lint>; using VVl = V<Vl>;
template< typename T > ostream& operator<<(ostream& os, const vector< T >& v) {
	for (int i = 0; i < (int)v.size(); i++) os << v[i] << (i + 1 != v.size() ? " " : "");
	return os;
}
template< typename T >istream& operator>>(istream& is, vector< T >& v) {
	for (T& in : v) is >> in;
	return is;
}
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
template <class T>
T div_floor(T a, T b) {
	if (b < 0) a *= -1, b *= -1;
	return a >= 0 ? a / b : (a + 1) / b - 1;
}
template <class T>
T div_ceil(T a, T b) {
	if (b < 0) a *= -1, b *= -1;
	return a > 0 ? (a - 1) / b + 1 : a / b;
}
template <class F> struct rec {
	F f;
	rec(F&& f_) : f(std::forward<F>(f_)) {}
	template <class... Args> auto operator()(Args &&... args) const {
		return f(*this, std::forward<Args>(args)...);
	}
};
lint gcd(lint a, lint b) { if (b == 0) return a; else return gcd(b, a % b); }
lint digit(lint a) { return (lint)log10(a); }
lint e_dist(plint a, plint b) { return abs(a.first - b.first) * abs(a.first - b.first) + abs(a.second - b.second) * abs(a.second - b.second); }
lint m_dist(plint a, plint b) { return abs(a.first - b.first) + abs(a.second - b.second); }
bool check_overflow(lint a, lint b, lint limit) { if (b == 0) return false; return a > limit / b; } // a * b > c => true
void Worshall_Floyd(VVl& g) { REP(k, SZ(g)) REP(i, SZ(g)) REP(j, SZ(g)) chmin(g[i][j], g[i][k] + g[k][j]); }
const lint MOD1000000007 = 1000000007, MOD998244353 = 998244353, INF = 1e18;
lint dx[8] = { 0, -1, 0, 1, 1, -1, 1, -1 }, dy[8] = { -1, 0, 1, 0, -1, -1, 1, 1 };
bool YN(bool flag) { cout << (flag ? "YES" : "NO") << endk; return flag; } bool yn(bool flag) { cout << (flag ? "Yes" : "No") << endk; return flag; }
struct Edge {
	lint from, to;
	lint cost, color;
	Edge() {

	}
	Edge(lint u, lint v, lint c, lint col) {
		cost = c;
		color = col;
		from = u;
		to = v;
	}
	bool operator<(const Edge& e) const {
		return cost < e.cost;
	}
};
struct WeightedEdge {
	lint to;
	lint cost, color;
	WeightedEdge(lint v, lint c, lint _color) {
		to = v;
		cost = c;
		color = _color;
	}
	bool operator<(const WeightedEdge& e) const {
		return cost < e.cost;
	}
};
using WeightedGraph = V<V<WeightedEdge>>;
typedef pair<plint, lint> tlint;
typedef pair<plint, plint> qlint;
typedef pair<lint, string> valstr;
typedef pair<ld, plint> _pld;
typedef pair<ld, lint> pidx;

lint N;
int main() {
	cin >> N;
	V<valstr> arr(N);
	REP(i, N) {
		lint T;
		string S;
		cin >> S >> T;
		arr[i] = { T, S };
	}
	sort(RALL(arr));
	cout << arr[1].second << endk;
}
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define ll long long
#define ln cout<<endl
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}void pr(){ln;}
template<class A,class...B>void pr(const A &a,const B&...b){cout<<a<<(sizeof...(b)?" ":"");pr(b...);}
template<class A>void PR(A a,ll n){rep(i,n)cout<<(i?" ":"")<<a[i];ln;}
const ll MAX=1e9+7,MAXL=1LL<<61,dx[8]={-1,0,1,0,-1,-1,1,1},dy[8]={0,1,0,-1,-1,1,1,-1};
typedef pair<ll,ll> P;

vector<string> rotate(vector<string> s) {
  int n=s.size(),m=s[0].size();
  vector<string> t(m);
  rep(i,m)rrep(j,n) t[i]+=s[j][i];
  return t;
}

ll n,m;
string s[1000];

ll calc(vector<string> t) {
  ll cnt=0;
  rep(k,m) {
    ll f=0;
    rep(l,2) {
      rep(i,n) {
        rep(j,n) {
          if(t[i].substr(0,s[k].size())==s[k]) f=1;
          rotate(t[i].begin(),t[i].begin()+1,t[i].end());
        }
      }
      t=rotate(t);
    }
    cnt+=f;
  }
  return cnt;
}

vector<string> ans;
ll MM;

void solve(vector<string> t) {
  ll d=calc(t);
  if(MM<d) {
    MM=d;
    ans=t;
  }
  rep(k,5) {
    random_shuffle(all(t));
    rep(i,n) rotate(t[i].begin(),t[i].begin()+rand()%n,t[i].end());
    ll d=calc(t);
    if(MM<d) {
      MM=d;
      ans=t;
    }
  }
}

void Main() {
  srand((unsigned)time(NULL));
  cin >> n >> m;
  rep(i,m) R s[i];
  vector<string> v[15];
  rep(i,m) v[s[i].size()].pb(s[i]);
  rep(e,30) {
    vector<string> t(n);
    rrep(i,15) {
      random_shuffle(all(v[i]));
      rep(j,v[i].size()) {
        ll M=MAX,x=0;
        string rr;
        rep(k,n) {
          rep(l,t[k].size()+1) {
            string r1=t[k].substr(l);
            if(r1.size()<=v[i][j].size()) {
              string r2=v[i][j].substr(0,r1.size());
              if(r1==r2) {
                ll d=t[k].size()+v[i][j].size()-r1.size();
                if(d<=n&&M>d) {
                  M=d;
                  x=k;
                  rr=t[k]+v[i][j].substr(r1.size());
                }
              }
            }
          }
        }
        if(rand()%6==0) M=MAX;
        if(M!=MAX) t[x]=rr;
      }
    }
    rep(i,n) {
      while(t[i].size()<n) {
        //t[i]+='.';
        t[i]+=(char)(rand()%8+'A');
      }
    }
    solve(t);
  }
  rep(i,n) pr(ans[i]);
}

int main(){Main();return 0;}
