#line 1 "library/my_template.hpp"
#if defined(LOCAL)
#include <my_template_compiled.hpp>
#else

// https://codeforces.com/blog/entry/96344
#pragma GCC optimize("Ofast,unroll-loops")
// いまの CF だとこれ入れると動かない？
// #pragma GCC target("avx2,popcnt")

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using i128 = __int128;
using u128 = unsigned __int128;
using f128 = __float128;

template <class T>
constexpr T infty = 0;
template <>
constexpr int infty<int> = 1'010'000'000;
template <>
constexpr ll infty<ll> = 2'020'000'000'000'000'000;
template <>
constexpr u32 infty<u32> = infty<int>;
template <>
constexpr u64 infty<u64> = infty<ll>;
template <>
constexpr i128 infty<i128> = i128(infty<ll>) * 2'000'000'000'000'000'000;
template <>
constexpr double infty<double> = infty<ll>;
template <>
constexpr long double infty<long double> = infty<ll>;

using pi = pair<ll, ll>;
using vi = vector<ll>;
template <class T>
using vc = vector<T>;
template <class T>
using vvc = vector<vc<T>>;
template <class T>
using vvvc = vector<vvc<T>>;
template <class T>
using vvvvc = vector<vvvc<T>>;
template <class T>
using vvvvvc = vector<vvvvc<T>>;
template <class T>
using pq = priority_queue<T>;
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;

#define vv(type, name, h, ...) vector<vector<type>> name(h, vector<type>(__VA_ARGS__))
#define vvv(type, name, h, w, ...) vector<vector<vector<type>>> name(h, vector<vector<type>>(w, vector<type>(__VA_ARGS__)))
#define vvvv(type, name, a, b, c, ...) \
  vector<vector<vector<vector<type>>>> name(a, vector<vector<vector<type>>>(b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))

// https://trap.jp/post/1224/
#define FOR1(a) for (ll _ = 0; _ < ll(a); ++_)
#define FOR2(i, a) for (ll i = 0; i < ll(a); ++i)
#define FOR3(i, a, b) for (ll i = a; i < ll(b); ++i)
#define FOR4(i, a, b, c) for (ll i = a; i < ll(b); i += (c))
#define FOR1_R(a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR2_R(i, a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR3_R(i, a, b) for (ll i = (b)-1; i >= ll(a); --i)
#define overload4(a, b, c, d, e, ...) e
#define overload3(a, b, c, d, ...) d
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FOR_R(...) overload3(__VA_ARGS__, FOR3_R, FOR2_R, FOR1_R)(__VA_ARGS__)

#define FOR_subset(t, s) for (ll t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s)))
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define elif else if

#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second

#define stoi stoll

int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(u32 x) { return __builtin_popcount(x); }
int popcnt(ll x) { return __builtin_popcountll(x); }
int popcnt(u64 x) { return __builtin_popcountll(x); }
int popcnt_sgn(int x) { return (__builtin_parity(x) & 1 ? -1 : 1); }
int popcnt_sgn(u32 x) { return (__builtin_parity(x) & 1 ? -1 : 1); }
int popcnt_sgn(ll x) { return (__builtin_parity(x) & 1 ? -1 : 1); }
int popcnt_sgn(u64 x) { return (__builtin_parity(x) & 1 ? -1 : 1); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int topbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2)
int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }

template <typename T>
T floor(T a, T b) {
  return a / b - (a % b && (a ^ b) < 0);
}
template <typename T>
T ceil(T x, T y) {
  return floor(x + y - 1, y);
}
template <typename T>
T bmod(T x, T y) {
  return x - y * floor(x, y);
}
template <typename T>
pair<T, T> divmod(T x, T y) {
  T q = floor(x, y);
  return {q, x - q * y};
}

template <typename T, typename U>
T SUM(const vector<U> &A) {
  T sm = 0;
  for (auto &&a: A) sm += a;
  return sm;
}

#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define LB(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define UB(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define UNIQUE(x) sort(all(x)), x.erase(unique(all(x)), x.end()), x.shrink_to_fit()

template <typename T>
T POP(deque<T> &que) {
  T a = que.front();
  que.pop_front();
  return a;
}
template <typename T>
T POP(pq<T> &que) {
  T a = que.top();
  que.pop();
  return a;
}
template <typename T>
T POP(pqg<T> &que) {
  T a = que.top();
  que.pop();
  return a;
}
template <typename T>
T POP(vc<T> &que) {
  T a = que.back();
  que.pop_back();
  return a;
}

template <typename F>
ll binary_search(F check, ll ok, ll ng, bool check_ok = true) {
  if (check_ok) assert(check(ok));
  while (abs(ok - ng) > 1) {
    auto x = (ng + ok) / 2;
    (check(x) ? ok : ng) = x;
  }
  return ok;
}
template <typename F>
double binary_search_real(F check, double ok, double ng, int iter = 100) {
  FOR(iter) {
    double x = (ok + ng) / 2;
    (check(x) ? ok : ng) = x;
  }
  return (ok + ng) / 2;
}

template <class T, class S>
inline bool chmax(T &a, const S &b) {
  return (a < b ? a = b, 1 : 0);
}
template <class T, class S>
inline bool chmin(T &a, const S &b) {
  return (a > b ? a = b, 1 : 0);
}

// ? は -1
vc<int> s_to_vi(const string &S, char first_char) {
  vc<int> A(S.size());
  FOR(i, S.size()) { A[i] = (S[i] != '?' ? S[i] - first_char : -1); }
  return A;
}

template <typename T, typename U>
vector<T> cumsum(vector<U> &A, int off = 1) {
  int N = A.size();
  vector<T> B(N + 1);
  FOR(i, N) { B[i + 1] = B[i] + A[i]; }
  if (off == 0) B.erase(B.begin());
  return B;
}

// stable sort
template <typename T>
vector<int> argsort(const vector<T> &A) {
  vector<int> ids(len(A));
  iota(all(ids), 0);
  sort(all(ids), [&](int i, int j) { return (A[i] == A[j] ? i < j : A[i] < A[j]); });
  return ids;
}

// A[I[0]], A[I[1]], ...
template <typename T>
vc<T> rearrange(const vc<T> &A, const vc<int> &I) {
  vc<T> B(len(I));
  FOR(i, len(I)) B[i] = A[I[i]];
  return B;
}

template <typename T, typename... Vectors>
void concat(vc<T> &first, const Vectors &... others) {
  vc<T> &res = first;
  (res.insert(res.end(), others.begin(), others.end()), ...);
}
#endif
#line 1 "library/other/io2.hpp"
#define INT(...)   \
  int __VA_ARGS__; \
  IN(__VA_ARGS__)
#define LL(...)   \
  ll __VA_ARGS__; \
  IN(__VA_ARGS__)
#define STR(...)      \
  string __VA_ARGS__; \
  IN(__VA_ARGS__)
#define CHR(...)    \
  char __VA_ARGS__; \
  IN(__VA_ARGS__)
#define DBL(...)           \
  long double __VA_ARGS__; \
  IN(__VA_ARGS__)

#define VEC(type, name, size) \
  vector<type> name(size);    \
  read(name)
#define VV(type, name, h, w)                     \
  vector<vector<type>> name(h, vector<type>(w)); \
  read(name)

void read(int &a) { cin >> a; }
void read(long long &a) { cin >> a; }
void read(char &a) { cin >> a; }
void read(double &a) { cin >> a; }
void read(long double &a) { cin >> a; }
void read(string &a) { cin >> a; }
template <class T, class S>
void read(pair<T, S> &p) {
  read(p.first), read(p.second);
}
template <class T>
void read(vector<T> &a) {
  for (auto &i: a) read(i);
}
template <class T>
void read(T &a) {
  cin >> a;
}
void IN() {}
template <class Head, class... Tail>
void IN(Head &head, Tail &... tail) {
  read(head);
  IN(tail...);
}

template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &A) {
  os << A.fi << " " << A.se;
  return os;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &A) {
  for (size_t i = 0; i < A.size(); i++) {
    if (i) os << " ";
    os << A[i];
  }
  return os;
}

// chatgpt helped me
class CoutInitializer {
public:
  CoutInitializer() { std::cout << std::fixed << std::setprecision(15); }
};
static CoutInitializer cout_initializer;

void print() {
  cout << "\n";
  cout.flush();
}

template <class Head, class... Tail>
void print(Head &&head, Tail &&... tail) {
  cout << head;
  if (sizeof...(Tail)) cout << " ";
  print(forward<Tail>(tail)...);
}

void YES(bool t = 1) { print(t ? "YES" : "NO"); }
void NO(bool t = 1) { YES(!t); }
void Yes(bool t = 1) { print(t ? "Yes" : "No"); }
void No(bool t = 1) { Yes(!t); }
void yes(bool t = 1) { print(t ? "yes" : "no"); }
void no(bool t = 1) { yes(!t); }
#line 3 "main.cpp"

#line 1 "library/string/split.hpp"
vc<string> split(string S, char sep = ',') {
  vc<string> res = {""};
  for (auto&& s: S) {
    if (s == sep)
      res.eb("");
    else
      res.back() += s;
  }
  return res;
}

vc<string> split(string S, string seps = " ,") {
  vc<string> res = {""};
  for (auto&& s: S) {
    if (count(all(seps), s))
      res.eb("");
    else
      res.back() += s;
  }
  return res;
}
#line 1 "library/string/trie.hpp"

// sigma が小さい
// 一般の n 頂点の木構造で O(n) 時間で動く
// https://atcoder.jp/contests/xmascontest2015noon/tasks/xmascontest2015_d
template <int sigma>
struct Trie {
  struct Node {
    array<int, sigma> ch;
    array<int, sigma> nxt; // suffix link -> add c
    int parent;
    int suffix_link;
  };
  int n_node;
  vc<Node> nodes;
  vc<int> words;
  vc<int> BFS; // BFS 順

  Trie() {
    n_node = 0;
    new_node();
  }

  Node& operator[](int i) { return nodes[i]; }

  template <typename STRING>
  int add(STRING S, int off) {
    int v = 0;
    for (auto&& s: S) { v = add_single(v, s, off); }
    words.eb(v);
    return v;
  }

  int add_single(int v, int c, int off) {
    c -= off;
    assert(0 <= c && c < sigma);
    if (nodes[v].ch[c] != -1) return nodes[v].ch[c];
    nodes[v].ch[c] = new_node();
    nodes.back().parent = v;
    return nodes[v].ch[c];
  }

  void calc_suffix_link() {
    BFS.resize(n_node);
    int p = 0, q = 0;
    BFS[q++] = 0;
    fill(all(nodes[0].nxt), 0);
    while (p < q) {
      int v = BFS[p++];
      if (v) nodes[v].nxt = nodes[nodes[v].suffix_link].nxt;
      FOR(s, sigma) {
        int w = nodes[v].ch[s];
        if (w == -1) continue;
        nodes[w].suffix_link = nodes[v].nxt[s];
        nodes[v].nxt[s] = w;
        BFS[q++] = w;
      }
    }
  }

  vc<int> calc_count() {
    vc<int> count(n_node);
    for (auto&& x: words) count[x]++;
    for (auto&& v: BFS)
      if (v) { count[v] += count[nodes[v].suffix_link]; }
    return count;
  }

private:
  int new_node() {
    Node c;
    fill(all(c.ch), -1);
    fill(all(c.nxt), -1);
    c.parent = -1;
    c.suffix_link = -1;
    nodes.eb(c);
    return n_node++;
  }
};
#line 2 "library/flow/mincostflow.hpp"

// atcoder library のものを改変
namespace internal {
template <class E>
struct csr {
  vector<int> start;
  vector<E> elist;
  explicit csr(int n, const vector<pair<int, E>>& edges) : start(n + 1), elist(edges.size()) {
    for (auto e: edges) { start[e.first + 1]++; }
    for (int i = 1; i <= n; i++) { start[i] += start[i - 1]; }
    auto counter = start;
    for (auto e: edges) { elist[counter[e.first]++] = e.second; }
  }
};

template <class T>
struct simple_queue {
  vector<T> payload;
  int pos = 0;
  void reserve(int n) { payload.reserve(n); }
  int size() const { return int(payload.size()) - pos; }
  bool empty() const { return pos == int(payload.size()); }
  void push(const T& t) { payload.push_back(t); }
  T& front() { return payload[pos]; }
  void clear() {
    payload.clear();
    pos = 0;
  }
  void pop() { pos++; }
};

} // namespace internal

/*
・atcoder library をすこし改変したもの
・DAG = true であれば、負辺 OK （1 回目の最短路を dp で行う）
ただし、頂点番号は toposort されていることを仮定している。
*/
template <class Cap = int, class Cost = ll, bool DAG = false>
struct Min_Cost_Flow {
public:
  Min_Cost_Flow() {}
  explicit Min_Cost_Flow(int n, int source, int sink) : n(n), source(source), sink(sink) {
    assert(0 <= source && source < n);
    assert(0 <= sink && sink < n);
    assert(source != sink);
  }

  // frm, to, cap, cost
  int add(int frm, int to, Cap cap, Cost cost) {
    assert(0 <= frm && frm < n);
    assert(0 <= to && to < n);
    assert(0 <= cap);
    assert(DAG || 0 <= cost);
    if (DAG) assert(frm < to);
    int m = int(_edges.size());
    _edges.push_back({frm, to, cap, 0, cost});
    return m;
  }

  void debug() {
    print("flow graph");
    print("frm, to, cap, cost");
    for (auto&& [frm, to, cap, flow, cost]: _edges) { print(frm, to, cap, cost); }
  }

  struct edge {
    int frm, to;
    Cap cap, flow;
    Cost cost;
  };

  edge get_edge(int i) {
    int m = int(_edges.size());
    assert(0 <= i && i < m);
    return _edges[i];
  }
  vector<edge> edges() { return _edges; }

  // (流量, 費用)
  pair<Cap, Cost> flow() { return flow(infty<Cap>); }
  // (流量, 費用)
  pair<Cap, Cost> flow(Cap flow_limit) { return slope(flow_limit).back(); }
  vector<pair<Cap, Cost>> slope() { return slope(infty<Cap>); }
  vector<pair<Cap, Cost>> slope(Cap flow_limit) {
    int m = int(_edges.size());
    vector<int> edge_idx(m);

    auto g = [&]() {
      vector<int> degree(n), redge_idx(m);
      vector<pair<int, _edge>> elist;
      elist.reserve(2 * m);
      for (int i = 0; i < m; i++) {
        auto e = _edges[i];
        edge_idx[i] = degree[e.frm]++;
        redge_idx[i] = degree[e.to]++;
        elist.push_back({e.frm, {e.to, -1, e.cap - e.flow, e.cost}});
        elist.push_back({e.to, {e.frm, -1, e.flow, -e.cost}});
      }
      auto _g = internal::csr<_edge>(n, elist);
      for (int i = 0; i < m; i++) {
        auto e = _edges[i];
        edge_idx[i] += _g.start[e.frm];
        redge_idx[i] += _g.start[e.to];
        _g.elist[edge_idx[i]].rev = redge_idx[i];
        _g.elist[redge_idx[i]].rev = edge_idx[i];
      }
      return _g;
    }();

    auto result = slope(g, flow_limit);

    for (int i = 0; i < m; i++) {
      auto e = g.elist[edge_idx[i]];
      _edges[i].flow = _edges[i].cap - e.cap;
    }

    return result;
  }

  // O(F(N+M)) くらい使って経路復元
  vvc<int> path_decomposition() {
    vvc<int> TO(n);
    for (auto&& e: edges()) { FOR(e.flow) TO[e.frm].eb(e.to); }
    vvc<int> res;
    vc<int> vis(n);

    while (!TO[source].empty()) {
      vc<int> path = {source};
      vis[source] = 1;
      while (path.back() != sink) {
        int to = POP(TO[path.back()]);
        while (vis[to]) { vis[POP(path)] = 0; }
        path.eb(to), vis[to] = 1;
      }
      for (auto&& v: path) vis[v] = 0;
      res.eb(path);
    }
    return res;
  }

  vc<Cost> get_potentials() { return potential; }

private:
  int n, source, sink;
  vector<edge> _edges;

  // inside edge
  struct _edge {
    int to, rev;
    Cap cap;
    Cost cost;
  };

  vc<Cost> potential;

  vector<pair<Cap, Cost>> slope(internal::csr<_edge>& g, Cap flow_limit) {
    if (DAG) assert(source == 0 && sink == n - 1);
    vector<pair<Cost, Cost>> dual_dist(n);
    vector<int> prev_e(n);
    vector<bool> vis(n);
    struct Q {
      Cost key;
      int to;
      bool operator<(Q r) const { return key > r.key; }
    };
    vector<int> que_min;
    vector<Q> que;
    auto dual_ref = [&]() {
      for (int i = 0; i < n; i++) { dual_dist[i].second = infty<Cost>; }
      fill(vis.begin(), vis.end(), false);
      que_min.clear();
      que.clear();

      // que[0..heap_r) was heapified
      size_t heap_r = 0;

      dual_dist[source].second = 0;
      que_min.push_back(source);
      while (!que_min.empty() || !que.empty()) {
        int v;
        if (!que_min.empty()) {
          v = que_min.back();
          que_min.pop_back();
        } else {
          while (heap_r < que.size()) {
            heap_r++;
            push_heap(que.begin(), que.begin() + heap_r);
          }
          v = que.front().to;
          pop_heap(que.begin(), que.end());
          que.pop_back();
          heap_r--;
        }
        if (vis[v]) continue;
        vis[v] = true;
        if (v == sink) break;
        Cost dual_v = dual_dist[v].first, dist_v = dual_dist[v].second;
        for (int i = g.start[v]; i < g.start[v + 1]; i++) {
          auto e = g.elist[i];
          if (!e.cap) continue;
          Cost cost = e.cost - dual_dist[e.to].first + dual_v;
          if (dual_dist[e.to].second > dist_v + cost) {
            Cost dist_to = dist_v + cost;
            dual_dist[e.to].second = dist_to;
            prev_e[e.to] = e.rev;
            if (dist_to == dist_v) {
              que_min.push_back(e.to);
            } else {
              que.push_back(Q{dist_to, e.to});
            }
          }
        }
      }
      if (!vis[sink]) { return false; }

      for (int v = 0; v < n; v++) {
        if (!vis[v]) continue;
        dual_dist[v].first -= dual_dist[sink].second - dual_dist[v].second;
      }
      return true;
    };

    auto dual_ref_dag = [&]() {
      FOR(i, n) dual_dist[i].se = infty<Cost>;
      dual_dist[source].se = 0;
      fill(vis.begin(), vis.end(), false);
      vis[0] = true;

      FOR(v, n) {
        if (!vis[v]) continue;
        Cost dual_v = dual_dist[v].fi, dist_v = dual_dist[v].se;
        for (int i = g.start[v]; i < g.start[v + 1]; i++) {
          auto e = g.elist[i];
          if (!e.cap) continue;
          Cost cost = e.cost - dual_dist[e.to].fi + dual_v;
          if (dual_dist[e.to].se > dist_v + cost) {
            vis[e.to] = true;
            Cost dist_to = dist_v + cost;
            dual_dist[e.to].second = dist_to;
            prev_e[e.to] = e.rev;
          }
        }
      }
      if (!vis[sink]) { return false; }

      for (int v = 0; v < n; v++) {
        if (!vis[v]) continue;
        dual_dist[v].fi -= dual_dist[sink].se - dual_dist[v].se;
      }
      return true;
    };

    Cap flow = 0;
    Cost cost = 0, prev_cost_per_flow = -1;
    vector<pair<Cap, Cost>> result = {{Cap(0), Cost(0)}};
    while (flow < flow_limit) {
      if (DAG && flow == 0) {
        if (!dual_ref_dag()) break;
      } else {
        if (!dual_ref()) break;
      }
      Cap c = flow_limit - flow;
      for (int v = sink; v != source; v = g.elist[prev_e[v]].to) { c = min(c, g.elist[g.elist[prev_e[v]].rev].cap); }
      for (int v = sink; v != source; v = g.elist[prev_e[v]].to) {
        auto& e = g.elist[prev_e[v]];
        e.cap += c;
        g.elist[e.rev].cap -= c;
      }
      Cost d = -dual_dist[source].first;
      flow += c;
      cost += c * d;
      if (prev_cost_per_flow == d) { result.pop_back(); }
      result.push_back({flow, cost});
      prev_cost_per_flow = d;
    }
    dual_ref();
    potential.resize(n);
    FOR(v, n) potential[v] = dual_dist[v].fi;
    return result;
  }
};
#line 7 "main.cpp"

int ctoi(char c) {
  if ('a' <= c && c <= 'z') return c - 'a';
  if ('A' <= c && c <= 'Z') return c - 'A' + 26;
  return -1;
}

char itoc[52];

void solve() {
  FOR(i, 26) itoc[i] = 'a' + i;
  FOR(i, 26) itoc[26 + i] = 'A' + i;

  string line;
  getline(cin, line);
  ll N = stoi(line);

  auto get = [&]() -> vc<string> {
    getline(cin, line);
    auto dat = split(line, " ,");
    Trie<52> trie;
    vc<int> dep = {0};
    vc<int> dp = {0};
    vc<int> last = {0};
    vc<int> vis = {0};
    auto new_node = [&](int w, int v, int c) -> void {
      if (w < len(dep)) return;
      assert(w == len(dep));
      dep.eb(dep[v] + 1);
      vis.eb(0);
      last.eb(c);
    };

    for (auto& S: dat) {
      pqg<tuple<int, int, int>> que;
      for (auto& v: dp) que.emplace(dep[v], v, 0);
      vc<int> newdp;
      while (len(que) && len(newdp) < N) {
        auto [d, v, k] = POP(que);
        if (k == len(S)) continue;
        int c = ctoi(S[k]);
        int w = trie.add_single(v, c, 0);
        new_node(w, v, c);
        if (!vis[w]) {
          vis[w] = 1;
          newdp.eb(w);
        }
        que.emplace(d + 1, w, k + 1);
      }
      swap(dp, newdp);
      for (auto& v: dp) vis[v] = 0;
    }

    // ふくげん
    vc<string> res;
    for (auto& v: dp) {
      string X;
      while (v > 0) {
        X += itoc[last[v]];
        v = trie[v].parent;
      }
      reverse(all(X));
      res.eb(X);
    }
    return res;
  };

  vvc<string> dat(N);
  FOR(i, N) {
    dat[i] = get();
    // print(i, dat[i]);
  }
  vc<string> key;
  FOR(i, N) concat(key, dat[i]);
  UNIQUE(key);
  int K = len(key);

  int s = 0;
  int t = N + K + 1;
  Min_Cost_Flow<int, int> G(t + 1, s, t);
  FOR(i, N) {
    for (auto& S: dat[i]) {
      int k = LB(key, S);
      G.add(1 + i, 1 + N + k, 1, 0);
    }
  }
  FOR(i, N) G.add(s, 1 + i, 1, 0);
  FOR(k, K) { G.add(1 + N + k, t, 1, len(key[k])); }
  // G.debug();

  auto [flow, cost] = G.flow(N);
  if (flow < N) return print("no solution");

  vc<string> ANS(N);

  for (auto& e: G.edges()) {
    if (e.flow == 0) continue;
    if (!(1 <= e.frm && e.frm <= N)) continue;
    if (!(N + 1 <= e.to && e.to <= N + K)) continue;
    int i = e.frm - 1;
    int k = e.to - (N + 1);
    // print("ik", i, k);
    ANS[i] = key[k];
  }
  FOR(i, N) print(ANS[i]);
}

signed main() {
  solve();
  return 0;
}