{"raw_statement":[{"iden":"statement","content":"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.\n\nMore 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$.\n\n$$\nv = \\max\\limits_{i \\in \\mathbb{S}, j \\in \\mathbb{S}, i \\ne j} \\text{lcp}(w_i, w_j)\n$$\n\nIn the above expression, $\\max$ is calculated by comparing the lexicographic order of strings.\n\nRecall that:\n- 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.\n- 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.\n- String $s$ is lexicographically smaller than string $t$ ($s \\ne t$), if\n  - $s$ is a prefix of $t$, or\n  - $s_{|p| + 1} < 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$.\n- Specifically, empty string is the string with the smallest lexicographic order."},{"iden":"input","content":"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:\n\nThe 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.\n\nFor 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.\n\nIt's guaranteed that the total length of all strings of all test cases will not exceed $10^6$."},{"iden":"output","content":"For each test case output one line containing one string indicating the answer. Specifically, if the answer is an empty string, print $\\texttt{EMPTY}$."}],"translated_statement":null,"sample_group":[["2\n5 3\ngdcpc\ngdcpcpcp\nsuasua\nsuas\nsususua\n3 3\na\nb\nc","gdcpc\nEMPTY"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}