Untitled

#include <ios>
#include <iostream>
#include <string>
#include <vector>

std::string res;
int FULL_MASK = 0;

int ALPHABET_SIZE = 26;

struct Node {
  uint32_t l;
  uint32_t r;
  int parent{-1};
  int link{-1};
  int shift{-1};
  std::vector<int> to;

  Node(uint32_t l, uint32_t r, int parent = -1)
      : l(l), r(r), parent(parent), to(ALPHABET_SIZE, -1) {}

  uint32_t size() const { return r - l; }
};

struct State {
  int node;
  uint32_t pos;

  State(int node, uint32_t pos) : node(node), pos(pos) {}
};

State transmit(State state, uint32_t l, uint32_t r, std::vector<Node> &nodes,
               const std::vector<uint8_t> &str) {
  while (l < r) {
    auto &node = nodes[state.node];

    if (state.pos == node.size()) {
      state.node = node.to[str[l]];
      state.pos = 0;

      if (state.node == -1) {
        return state;
      }
    } else {
      if (str[node.l + state.pos] != str[l]) {
        return State(-1, 0);
      }

      if (r - l < node.size() - state.pos) {
        return State(state.node, state.pos + r - l);
      }

      l += node.size() - state.pos;
      state.pos = node.size();
    }
  }

  return state;
}

uint32_t split(const State &state, std::vector<Node> &nodes,
               const std::vector<uint8_t> &str) {
  auto &node = nodes[state.node];

  if (state.pos == node.size()) {
    return state.node;
  }

  if (state.pos == 0) {
    return node.parent;
  }

  uint32_t id = nodes.size();
  nodes.emplace_back(node.l, node.l + state.pos, node.parent);

  nodes[node.parent].to[str[node.l]] = id;
  nodes[id].to[str[node.l + state.pos]] = state.node;

  node.parent = id;
  node.l += state.pos;
  return id;
}

int get_link(int node_id, std::vector<Node> &nodes,
             const std::vector<uint8_t> &str) {
  auto &node = nodes[node_id];

  if (node.link != -1) {
    return node.link;
  }

  if (node.parent == -1) {
    return 0;
  }

  auto to = get_link(node.parent, nodes, str);
  auto state = transmit(State(to, nodes[to].size()),
                        node.l + (node.parent == 0), node.r, nodes, str);
  node.link = split(state, nodes, str);
  return node.link;
}

void add(int pos, State &state, std::vector<Node> &nodes,
         const std::vector<uint8_t> &str) {
  while (true) {
    auto st = transmit(state, pos, pos + 1, nodes, str);

    if (st.node != -1) {
      state = st;
      return;
    }

    int mid = split(state, nodes, str);
    auto leaf = nodes.size();
    nodes.emplace_back(pos, str.size(), mid);
    nodes[mid].to[str[pos]] = leaf;

    nodes[leaf].shift = pos - nodes[mid].size();

    state.node = get_link(mid, nodes, str);
    state.pos = nodes[state.node].size();

    if (mid == 0) {
      nodes[leaf].shift = pos;
      break;
    }
  }
}

int func(int n, const std::vector<Node> &nodes, const std::vector<uint8_t> &str,
         std::string &tmp) {
  const auto &node = nodes[n];
  size_t size = tmp.size();

  int mask = 0;

  for (uint32_t i = node.l; i < node.r; ++i) {
    if (mask == 0 && str[i] < 26) {
      tmp.push_back(str[i] + 'a');
    }

    if (str[i] >= 26) {
      mask |= (1 << (str[i] - 26));
      break;
    }
  }

  if (mask != 0) {
    if (size < tmp.size()) {
      tmp.resize(size);
    }

    return mask;
  }

  for (int i = 0; i < node.to.size(); ++i) {
    if (node.to[i] != -1) {
      mask |= func(node.to[i], nodes, str, tmp);
    }
  }

  if (mask == FULL_MASK && res.size() < tmp.size()) {
    res = tmp;
  }

  if (size < tmp.size()) {
    tmp.resize(size);
  }

  return mask;
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  int K;
  std::cin >> K;

  ALPHABET_SIZE += K;

  std::vector<uint8_t> str(200001 * K, 0);
  int size = 0;
  char ch;
  std::cin.get(ch);

  while (K > 0) {
    std::cin.get(ch);

    if (ch == '\n') {
      FULL_MASK <<= 1;
      FULL_MASK |= 1;

      --K;
      str[size] = K + 26;
      ++size;
      continue;
    }

    str[size] = ch - 'a';
    ++size;
  }

  str.resize(size);
  State state(0, 0);

  std::vector<Node> nodes;
  nodes.reserve(size * 2);
  nodes.emplace_back(0, 0, -1);

  for (size_t i = 0; i < str.size(); ++i) {
    add(i, state, nodes, str);
  }

  std::string tmp;
  tmp.reserve(200000);
  func(0, nodes, str, tmp);

  std::cout << res << "\n";
  return 0;
}