该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定 $n$ 个只包含小写字母的字符串 $s_1, s_2,...,s_n$，和一个正整数 $k$。

伞伞 从这 $n$ 个字符串中选出了 $k$ 个字符串组成集合 $S$。

设 $S$ 中任意两个字符串的最长公共前缀长度最大为 $L$，则 $S$ 的核心串定义为一个字符串 $t$，满足以下所有条件：

• $t$ 的长度恰好为 $L$
• $t$ 是 $S$ 中至少两个字符串的公共前缀
• $t$ 的字典序是满足前两个条件中最小的

问 伞伞 选择的所有可能的集合中，字典序最小的核心串是哪个字符串？

特别地，空串字典序最小。

输入格式

从文件 core.in 读入数据。 第一行一个正整数 $T$ 表示包含 $T$ 组测试数据，对于每组测试数据：

第一行两个正整数 $n$，$k$，表示字符串数量和集合 $S$ 中的字符串数量。

接下来 $n$ 行，每行一个字符串 $s_i$。

输出格式

输出到文件 core.out。 一个字符串，表示答案。特别地，如果答案为空串，则输出 EMPTY。

4
4 3
abc
bc
abc
ac
4 2
abc
bc
abc
ac
8 4
bvyavo
bwr
bwvoqjbtx
bw
bwpfopp
bwrt
bvyassrqusapir
bwvuu
9 7
qoanvoe
grqsq
qoanve
guajgbe
grqsqj
grqsl
isoax
qoa
grqslz

a
EMPTY
bvya
grqsl

解释

在第一组数据中，选取 $bc,abc,ac$ 组成集合 $S$，其核心串为 $a$。

在第二组数据中，选取 $abc,bc$ 组成集合 $S$，其核心串为空串，因为这两个字符串没有公共前缀。

数据规模与约定

下发文件

下发文件分别对应子任务 $1,2,3,4,5$。

对于 $100\%$ 的数据：保证 $1 \leq T \leq 10,2 \leq n,\sum n \leq 2 \times 10^{5},2 \leq k \leq n$，所有字符串只由小写字母构成，所有字符串总长度不超过 $2 \times 10^5$。

时空限制：$1$ 秒 / $256\,\mathrm{MiB}$。