Hide

Problem G
Central String

You have a collection of strings of the same length L and are wondering how similar they are. We can say that the distance d(S,T) between two strings S and T of the same length is the number of indices i where SiTi. For example, d(berry,bears)=2 since only the third and fifth characters differ.

You wonder if your strings are very close to each other. That is, for a given distance D you have in mind, is there a string S of length L such that d(S,A)D for each string A in your collection? Call such a string S a central string. Note that a central string does not necessarily have to be one of your strings.

Input

The first line of input contains three integers N (1N50), L (1L1000000), and D (0D6). Here, N indicates the number of strings in your collection, L is the common length of these strings, and D is the distance bound you are curious about. Then N lines follow, the i’th such line contains a single string Ai of length L consisting of only lowercase letters.

You are further guaranteed that NL1000000.

Output

Output consists of a single line. If there is a string S consisting of only lowercase letters such that d(S,Ai)D for each 1iN, output any such string. Otherwise, simply output the single digit 0 to indicate there is no central string.

Sample Input 1 Sample Output 1
2 4 1
abba
bbca
abca
Sample Input 2 Sample Output 2
3 4 3
abcd
efgh
ijkl
abgl
Sample Input 3 Sample Output 3
3 4 2
abcd
efgh
ijkl
0
Hide

Please log in to submit a solution to this problem

Log in