E. New but Nostalgic Problem
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Given $$$n$$$ strings $$$w_1, w_2, \cdots, w_n$$$, please select $$$k$$$ strings among them, so that the lexicographic order of string $$$v$$$ is minimized, and output the optimal string $$$v$$$. String $$$v$$$ satisfies the following constraint: $$$v$$$ is the longest common prefix of two selected strings with different indices. Also, $$$v$$$ is the lexicographically largest string among all strings satisfying the constraint.

More formally, let $$$\mathbb{S}$$$ be a set of size $$$k$$$, where all the elements in the set are integers between $$$1$$$ and $$$n$$$ (both inclusive) and there are no duplicated elements. Let $$$\text{lcp}(w_i, w_j)$$$ be the longest common prefix of string $$$w_i$$$ and $$$w_j$$$, please find a set $$$\mathbb{S}$$$ to minimize the lexicographic order of the following string $$$v$$$ and output the optimal string $$$v$$$.

$$$$$$ v = \max\limits_{i \in \mathbb{S}, j \in \mathbb{S}, i \ne j} \text{lcp}(w_i, w_j) $$$$$$

In the above expression, $$$\max$$$ is calculated by comparing the lexicographic order of strings.

Recall that:

  • String $$$p$$$ is a prefix of string $$$s$$$, if we can append some number of characters (including zero characters) at the end of $$$p$$$ so that it changes to $$$s$$$. Specifically, empty string is a prefix of any string.
  • The longest common prefix of string $$$s$$$ and string $$$t$$$ is the longest string $$$p$$$ such that $$$p$$$ is a prefix of both $$$s$$$ and $$$t$$$. For example, the longest common prefix of "abcde" and "abcef" is "abc", while the longest common prefix of "abcde" and "bcdef" is an empty string.
  • String $$$s$$$ is lexicographically smaller than string $$$t$$$ ($$$s \ne t$$$), if
    • $$$s$$$ is a prefix of $$$t$$$, or
    • $$$s_{|p| + 1} \lt t_{|p| + 1}$$$, where $$$p$$$ is the longest common prefix of $$$s$$$ and $$$t$$$, $$$|p|$$$ is the length of $$$p$$$, $$$s_i$$$ is the $$$i$$$-th character of string $$$s$$$, and $$$t_i$$$ is the $$$i$$$-th character of string $$$t$$$.
    Specifically, empty string is the string with the smallest lexicographic order.
Input

There are multiple test cases. The first line of the input contains an integer $$$T$$$ indicating the number of test cases. For each test case:

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2\leq n\leq 10^6$$$, $$$2\leq k\leq n$$$) indicating the total number of strings and the number of strings to be selected.

For the following $$$n$$$ lines, the $$$i$$$-th line contains a string $$$w_i$$$ ($$$1\leq |w_i|\leq 10^6$$$) consisting of lower-cased English letters.

It's guaranteed that the total length of all strings of all test cases will not exceed $$$10^6$$$.

Output

For each test case output one line containing one string indicating the answer. Specifically, if the answer is an empty string, print EMPTY.

Example
Input
2
5 3
gdcpc
gdcpcpcp
suasua
suas
sususua
3 3
a
b
c
Output
gdcpc
EMPTY