CFCF2194C.Secret message

题目描述

天才间谍鲍勃截获了一条加密信息。他推测其中包含秘密情报，并正积极致力于破解它。

落入间谍手中的纸条由 $k$ 条组成，每条长度为 $n$，包含严格的小写拉丁字母。凭借解密此类文档的丰富经验，鲍勃猜测他感兴趣的消息（即纸条的解密）也是一个长度为 $n$ 的字符串，并且该消息的第 $i$ 个字母对应于某条纸条的第 $i$ 个字母。

鲍勃定义字符串 $s$ 的信息性为最小的正整数 $d$，使得存在一个长度为 $d$ 的字符串 $t$，并且 $s$ 可以通过重复 $t$ 若干次来形成。例如，字符串 "aaaa" 的信息性是 $1$，字符串 "abab" 的信息性是 $2$，字符串 "abcd" 的信息性是 $4$。

鲍勃推测，笔记的作者为了确保信息可靠传输，将消息中的数据重复了多次。因此，他认为更合理的解密应该是具有最小可能信息性的。

帮助间谍：找到代表笔记解密的消息，且具有最小可能信息性。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t（1 \le t \le 10^4）$。随后是测试用例的描述。

每个测试用例的第一行有数字 $n$ 和 $k$ $(2 \le n,k \le 50000, 4 \le n·k \le 10^5)$—— 纸条的长度和纸条的数量。

在每个测试用例的接下来 $k$ 行中，每行有一个由 $n$ 个小写拉丁字母组成的序列 —— 下一个纸条。

保证所有测试用例的 $n·k$ 总和不超过 $10^5$。

输出格式

对于每个测试用例，输出一个长度为 $n$ 的字符串 —— 笔记的解密，具有最小可能信息性。如果有多个合适的答案，可以输出其中任何一个。

说明/提示
在第一个测试用例中，最小可能信息性是 1：

abc

baa

解密为aaa

在第二个测试用例中，最小可能信息性是 3：

iiinnnfff

nnfiffinn

解密为infinfinf