A16734. Secret message
编程题
普及+/提高
知识点
题目描述
天才间谍鲍勃截获了一条加密信息。他推测其中包含秘密情报，并正积极致力于破解它。
落入间谍手中的纸条由 $k$ 条组成，每条长度为 $n$，包含严格的小写拉丁字母。凭借解密此类文档的丰富经验，鲍勃猜测他感兴趣的消息（即纸条的解密）也是一个长度为 $n$ 的字符串，并且该消息的第 $i$ 个字母对应于某条纸条的第 $i$ 个字母。
鲍勃定义字符串 $s$ 的信息性为最小的正整数 $d$，使得存在一个长度为 $d$ 的字符串 $t$，并且 $s$ 可以通过重复 $t$ 若干次来形成。例如，字符串 "aaaa" 的信息性是 $1$，字符串 "abab" 的信息性是 $2$，字符串 "abcd" 的信息性是 $4$。
鲍勃推测，笔记的作者为了确保信息可靠传输，将消息中的数据重复了多次。因此，他认为更合理的解密应该是具有最小可能信息性的。
帮助间谍：找到代表笔记解密的消息，且具有最小可能信息性。
落入间谍手中的纸条由 $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$。
每个测试包含多个测试用例。第一行包含测试用例的数量 $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$ 的字符串 —— 笔记的解密，具有最小可能信息性。如果有多个合适的答案，可以输出其中任何一个。
对于每个测试用例，输出一个长度为 $n$ 的字符串 —— 笔记的解密，具有最小可能信息性。如果有多个合适的答案，可以输出其中任何一个。
输入输出样例
输入 #1
3 3 2 abc baa 9 2 iiinnnfff nnfiffinn 4 2 acbd bdac
输出 #1
aaa infinfinf acac
说明/提示
说明/提示
在第一个测试用例中，最小可能信息性是 1：
abc
baa
解密为aaa
在第二个测试用例中，最小可能信息性是 3：
iiinnnfff
nnfiffinn
解密为infinfinf
在第一个测试用例中，最小可能信息性是 1：
abc
baa
解密为aaa
在第二个测试用例中，最小可能信息性是 3：
iiinnnfff
nnfiffinn
解密为infinfinf