题目描述

你可能好奇过为什么大多数外星生命形态看起来都像人类，只是在身高、肤色、皱纹、耳朵、眉毛等表面特征上有所不同。也有少数生命形态与人类毫无相似之处；这些通常具有几何形状或不定形形状，如立方体、油膜或尘埃云。

《星际迷航：下一代》第 146 集《追逐》（The Chase）给出了答案。结果表明，本象限中绝大多数生命体最终都拥有很大一部分相同的 DNA 片段。

给定若干个生命体的 DNA 序列（用字母字符串表示），你需要找到一个最长的子串，使得该子串在超过一半的生命体 DNA 序列中出现。

输入格式

标准输入包含多组测试数据。

每组测试数据的第一行包含一个整数 $n$ ($1 \le n \le 100$)，表示生命体的数量。 接下来 $n$ 行，每行包含一个由小写字母组成的字符串，代表一个生命体的 DNA 序列。每个 DNA 序列的长度至少为 $1$ 且不超过 $2000$。 输入以一行包含单独一个 $0$ 作为结束标志，该行不处理。

输出格式

对于每组测试数据，输出在超过一半（严格大于 $\lfloor n/2 \rfloor$ 个）的生命体中出现过的最长子串。

• 如果有多个长度相同的最长子串，请按字典序从小到大输出所有这些子串（每行一个）。
• 如果不存在长度至少为 $1$ 的解，输出 ?。
• 注意： 在相邻两组测试数据的输出之间应输出一个空行。

3
abcdefg
bcdefgh
cdefghi
3
xxx
yyy
zzz
0

bcdefg
cdefgh

?