Hide

Problem K
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 $S_ i \neq T_ i$. For example, $d(\texttt{berry}, \texttt{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) \leq 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$ ($1 \leq N \leq 50$), $L$ ($1 \leq L \leq 1\, 000\, 000$), and $D$ ($0 \leq D \leq 6$). 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 $A_ i$ of length $L$ consisting of only lowercase letters.

You are further guaranteed that $N \cdot L \leq 1\, 000\, 000$.

Output

Output consists of a single line. If there is a string $S$ consisting of only lowercase letters such that $d(S,A_ i) \leq D$ for each $1 \leq i \leq N$, 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

Please log in to submit a solution to this problem

Log in