P9694 [GDCPC 2023] New but Nostalgic Problem

给定 $n$ 个字符串 $w_1, w_2, \cdots, w_n$，请选出恰好 $k$ 个字符串，最小化字符串 $v$ 的字典序，并输出这个最优的字符串 $v$。其中 $v$ 满足以下条件：$v$ 是被选出的字符串中，某两个编号不同的字符串的最长公共前缀。而且，$v$ 是所有满足条件的字符串中，字典序最大的字符串。 更正式地，令 $\mathbb{S}$ 表示一个大小为 $k$ 的集合，集合中的元素均为从 $1$ 到 $n$ 的整数（含两端），且没有重复的元素。令 $\text{lcp}(w_i, w_j)$ 表示字符串 $w_i$ 和 $w_j$ 的最长公共前缀，您需要找到一个集合 $\mathbb{S}$ 以最小化下述字符串 $v$ 的字典序，并输出这个最优的字符串 $v$。 $$ v = \max\limits_{i \in \mathbb{S}, j \in \mathbb{S}, i \ne j} \text{lcp}(w_i, w_j) $$ 上式中的 $\max$ 通过字典序比较两个字符串。 请回忆： - 称字符串 $p$ 是字符串 $s$ 的前缀，若可以在 $p$ 的末尾添加若干个字符（包括零个字符）将它变成 $s$。特别地，空字符串是任意字符串的前缀。 - 字符串 $s$ 和 $t$ 的最长公共前缀是一个最长的字符串 $p$，满足 $p$ 既是 $s$ 的前缀，又是 $t$ 的前缀。例如，``abcde`` 与``abcef`` 的最长公共前缀为 ``abc``，而 ``abcde`` 与 ``bcdef`` 的最长公共前缀为空字符串。 - 称字符串 $s$ 的字典序小于字符串 $t$（$s \ne t$），若 - $s$ 是 $t$ 的前缀，或 - $s_{|p| + 1} < t_{|p| + 1}$，其中 $p$ 为 $s$ 和 $t$ 的最长公共前缀，$|p|$ 为 $p$ 的长度，$s_i$ 表示字符串 $s$ 的第 $i$ 个字符，$t_i$ 表示字符串 $t$ 的第 $i$ 个字符。 - 特别地，空字符串是字典序最小的字符串。

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数。对于每组测试数据： 第一行输入两个整数 $n$ 和 $k$（$2\leq n\leq 10^6$，$2\leq k\leq n$），表示字符串的总数和需要选择的字符串的数量。 对于接下来 $n$ 行，第 $i$ 行输入一个由小写字母构成的字符串 $w_i$（$1\leq |w_i|\leq 10^6$）。 保证所有数据中字符串长度之和不超过 $10^6$。

每组数据输出一行一个字符串表示答案。特别地，若答案为空字符串，输出 $\texttt{EMPTY}$。