#!/usr/bin/env python3 # Thanks: http://hamayanhamayan.hatenablog.jp/entry/2017/05/29/013706 import array import heapq import itertools class TopologicalSortError(Exception): pass def topological_sort(num_vs, adj_vs): """ Performs topological sorting of the given DAG. This function computes the lexicographically least topological order of the given DAG. :param num_vs int: The number of vertices. :param adj_vs list: The adjacency list. :return: The lexicographically least topological order. :rtype: :obj:`array.array` :raises TopologicalSortError: if the given graph is not a DAG """ in_deg = array.array("L", (0 for _ in range(num_vs))) for dests in adj_vs: for dest in dests: in_deg[dest] += 1 sorted_vs = array.array("L") pq = [] for s in range(num_vs): if in_deg[s] == 0: heapq.heappush(pq, s) while pq: u = heapq.heappop(pq) sorted_vs.append(u) for v in adj_vs[u]: in_deg[v] -= 1 if in_deg[v] == 0: heapq.heappush(pq, v) if all(x == 0 for x in in_deg): return sorted_vs else: raise TopologicalSortError("The graph has a cycle") def solve(yukis, kodas): all_chars = "".join(sorted(itertools.chain(*yukis))) num_vs = len(all_chars) char_to_idx = dict() for i, c in enumerate(all_chars): # 文字 -> 頂点番号の対照表 char_to_idx[c] = i adj_vs = [set() for _ in range(num_vs)] for frag in itertools.chain(yukis, kodas): for c1, c2 in zip(frag[:-1], frag[1:]): # 隣接する二つの文字c1, c2について # c1 -> c2という有向辺があると考える adj_vs[char_to_idx[c1]].add(char_to_idx[c2]) try: res = topological_sort(num_vs, adj_vs) except TopologicalSortError: return None for i, j in zip(res[:-1], res[1:]): # ソートされた頂点の列において、 # どの隣接する2頂点の間にも辺があるか? if j not in adj_vs[i]: return None return "".join(all_chars[i] for i in res) def main(): n = int(input()) yukis = [input() for _ in range(n)] m = int(input()) kodas = [input() for _ in range(m)] ans = solve(yukis, kodas) if ans is None: print(-1) else: print(ans) if __name__ == '__main__': main() #    ∧    /| #   / ∧__/ | #  / _   _ ヽ # `/ く◎> く◎〉| # |   ̄    ̄ | # 人       ノ  _ #  \___  /  || #   /   ̄| ̄   || #   /    ヽ___ノ| #  |         / #  | /|      | #   L/ |  /|    / #     |_/ | /|  / #       |/ ヽ/