405869: GYM102136 K Slogan

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

K. Slogantime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

The company «42 shades of green» consists of N departments. To increase team spirit, the company's management asked each department to come up with a slogan, which is a string consisting of at least K lower-case Englsih characters. To assess the work of all departments of the company it was decided to choose a lexicographically minimal string that would contain at least one substring of length K from the slogans of each of the departments as a common slogan. Since the budget for printing a slogan is limited, it should not contain unnecessary characters. So let's consider for each department slogan the first occurrence of any substring of length K in the general slogan and if there is a symbol that is not covered by these occurrences, then such symbol is unnecessary and it needs to be deleted.

Help the company «42 shades of green» find their corporate slogan from the specified slogans of departments.

Input

The first line contains two integers N and K — number of departments and length of substrings.

Each following N lines contain string Si — slogan of the i-th department.

1 ≤ N ≤ 1000
1 ≤ K ≤ 100
K ≤ |Si|
Output

In the only line, output the corporate slogan of the company.

ExamplesInput
5 3
abacabada
abada
dada
cadaca
adac
Output
abaacaada
Input
5 3
abacabada
abada
daada
cadaca
adac
Output
aada

加入题单

上一题 下一题 算法标签: