题目描述

给你 $n$ 个字符串 $s_1,s_2,...,s_n$，对于第 $i$ 个字符串 $s_i$，有 $|s_i|$ 个前缀。现在我们要把所有这 $n$ 个字符串的所有前缀按字典序大小排序，请求出字典序第 $k$ 大的前缀。

输入格式

第一行两个整数 $n,k$。

接下来 $n$ 行，第 $i$ 行一个由小写字母构成的字符串 $s_i$。

输出格式

输出一行一个字符串表示答案。

4 10
abcd
cdf
abc
bbc

bbc

数据规模

对于所有数据，保证 $1≤n≤1000000, 1≤|s_i|≤1000000, 1≤k≤\sum_{i=1}^{n} |s_i|≤1000000$, 字符串均由小写字母构成。