Untitled

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

struct Result {
  size_t size{0};
  std::list<std::pair<uint32_t, uint32_t>> items;
};

Result out;
int FULL_MASK = 0;

int ALPHABET_SIZE = 26;

struct Node {
  uint32_t l;
  uint32_t r;
  int parent{-1};
  int link{-1};
  int number{-1};
  std::unordered_map<uint8_t, uint32_t> to;

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

  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()) {
      auto it = node.to.find(str[l]);
      state.node = it == node.to.end() ? -1 : it->second;
      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 number, 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].number = number;

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

    if (mid == 0) {
      break;
    }
  }
}

bool compare(const Result &v1, const Result &v2,
             const std::vector<uint8_t> &str) {

  uint32_t l1 = v1.items.front().first;
  uint32_t r1 = v1.items.front().second;
  uint32_t l2 = v2.items.front().first;
  uint32_t r2 = v2.items.front().second;

  auto it1 = v1.items.begin();
  auto it2 = v2.items.begin();

  while (it1 != v1.items.end() && it2 != v2.items.end()) {
    if (l1 >= r1) {
      ++it1;

      if (it1 == v1.items.end()) {
        break;
      }

      l1 = it1->first;
      r1 = it2->second;
    }

    if (l2 >= r2) {
      ++it2;

      if (it2 == v2.items.end()) {
        break;
      }

      l2 = it2->first;
      r2 = it2->second;
    }

    if (str[l1] == str[l2]) {
      ++l1;
      ++l2;
      continue;
    }

    return str[l1] > str[l2];
  }

  return false;
}

int func(int n, const std::vector<Node> &nodes, const std::vector<uint8_t> &str,
         Result &res) {
  const auto &node = nodes[n];

  if (node.number == -1) {
    if (node.size() > 0) {
      res.size += node.size();
      res.items.emplace_back(node.l, node.r);
    }

    int mask = 0;
    for (auto it = node.to.begin(); it != node.to.end(); ++it) {
      mask |= func(it->second, nodes, str, res);
    }

    if (mask == FULL_MASK && res.size > 0 &&
        (res.size > out.size ||
         (res.size == out.size && compare(res, out, str)))) {
      out = res;
    }

    if (node.size() > 0) {
      res.size -= node.size();
      res.items.pop_back();
    }

    return mask;
  } else {
    return (1 << node.number);
  }
}

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

  int K;
  std::cin >> K;

  std::string s;
  std::getline(std::cin, s);

  if (K == 1) {
    std::getline(std::cin, s);
    std::cout << s << "\n";
    return 0;
  }

  ALPHABET_SIZE += K;

  std::vector<uint8_t> str;
  size_t size = K;

  {
    std::vector<std::string> data(K, std::string());

    for (int i = 0; i < K; ++i) {
      s.reserve(200000);
      std::getline(std::cin, s);
      size += s.size();
      std::swap(data[i], s);

      FULL_MASK <<= 1;
      FULL_MASK |= 1;
    }

    str.resize(size, 0);
    int index = 0;

    for (int i = 0; i < K; ++i) {
      for (size_t j = 0; j < data[i].size(); ++j) {
        str[index] = data[i][j] - 'a';
        ++index;
      }

      str[index] = i + 26;
      ++index;
    }
  }

  State state(0, 0);

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

  int number = ALPHABET_SIZE - 27;

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

    if (str[i] >= 26) {
      --number;
    }
  }

  Result res;
  func(0, nodes, str, res);

  if (out.size > 0) {
    for (auto it = out.items.begin(); it != out.items.end(); ++it) {
      for (uint32_t begin = it->first; begin < it->second; ++begin) {
        std::cout << static_cast<char>('a' + str[begin]);
      }
    }
  }

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