Description

给定 \(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\) 个字符。 特别地，空字符串是字典序最小的字符串。

Input

有多组测试数据。第一行输入一个整数 \(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\)。

Output

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

2
5 3
gdcpc
gdcpcpcp
suasua
suas
sususua
3 3
a
b
c

gdcpc
EMPTY