Minimizing the Maximum Common Prefix

You are given n strings w₁, w₂, ..., w_n and an integer k (k ≥ 2). Your task is to select k strings from the given list (each string is identified by its index from 1 to n, and no index is repeated) such that if we define

$$ v = \max_{\substack{i,j \in \mathbb{S} \\ i \ne j}} \textrm{lcp}(w_i, w_j), $$

where lcp(a,b) denotes the longest common prefix of strings a and b (with the usual definition that the empty string is a prefix of any string and is considered the smallest lexicographically), then the string v is minimized in lexicographic order.

</p>

In other words, among all possible subsets \(\mathbb{S}\) of indices of size k, each inducing a value v defined as the lexicographically largest longest common prefix among all pairs of distinct strings in the subset, you must choose one that minimizes v (according to lexicographic order). Finally, output the optimal string v.

Recall:

• A string p is a prefix of a string s if we can append zero or more characters to p to obtain s.
• The longest common prefix of s and t is the longest string p such that p is a prefix of both s and t.
• For two distinct strings s and t, s is lexicographically smaller than t if either s is a prefix of t or if at the first position where they differ, the character in s is smaller than the character in t. By definition, the empty string is the smallest lexicographically.

inputFormat

The first line of input contains two integers n and k (k ≥ 2).

The following n lines each contain a non-empty string consisting of lowercase letters.

outputFormat

Output the optimal string v that is obtained from the selected subset. Note that v is defined as the lexicographically largest longest common prefix among every pair of strings in the subset, and the goal is to choose the subset so that v is minimized in lexicographic order.

sample

3 2
abcde
abcef
xyz

</p>