思路概述

我们把“等价”理解为字符多重集合相同（即字母出现次数一致、顺序无关）。 对每个字符串 $s_i$ ，只要它包含某个字母 $c$ 至少 $x$ 次，就能从中挑出 $x$ 个 $c$ 作为子序列的一部分。于是：

• 若要存在同一个字符串 $t$ 被每个 $s_i$ 的某个子序列“等价”，那么对每个字母 $c$，在 $t$ 中的出现次数 $\text{cnt}_t[c]$ 不能超过所有字符串中该字母出现次数的最小值：

  $$\text{cnt}_t[c] \le \min_i \text{cnt}_{s_i}[c]$$

本题为2025年8月31日得物机考原题

得物机考的介绍点击这里

题目内容

定义两个字符串是等价的，当且仅当其中一个串可以通过重新排列这些字符得到另一个串。例如，$abccb$和$cbcba$等价，$a$和$a$等价，$abba$和$baab$等价。而$abc$和$aac$不等价，$a$和$b$不等价。

现在输入$n$个仅由小写字母组成的字符串$s_1,s_2,…,s_n$，你需要找到一个长度最长的字符串$t$，使得每个串都能找到一个子序列，这个子序列形成的字符串与$t$等价。

如果有多个答案，请输出字典序最小的串。如果找不到，则输出$-1$。

输入描述

第一行输入一个正整数$T(1≤T≤5)$，表示数据组数。

对于每一组数据:

第一行输入一个正整数$n(1≤n≤10^4)$，表示字符串的个数。

第二行输入$n$个仅由小写字母组成的字符串$s_1,s_2,...s_n$，每两个字符串之间用一个空格隔开，末尾没有多余空格。

保证同一组数据的字符串长度之和不超过$10^5$。

输出描述

对于每一组数据，输出一行。如果有多个答案，请输出字典序最小的串。如果找不到，则输出$-1$。

样例1

输入

2
3
path photo hope
2
abc def

输出

hp
-1