- Time limit: 1.00 s
- Memory limit: 512 MB
- add one character
- remove one character
- change one character
Given three strings $a$, $b$ and $c$, your task is to find a string $x$ such that $d(x,a)+d(x,b)+d(x,c)$ is minimum.
Input
There are three lines that contain the strings $a$, $b$ and $c$. Each string consists of characters $\texttt{A} \ldots \texttt{Z}$.
Output
Print a string $x$ that consists of characters $\texttt{A} \ldots \texttt{Z}$ and minimizes the edit distance. If there are several such strings, print any of them.
Constraints
- $1 \le |a|, |b|, |c| \le 50$
Input:
ABBA
AYBABTU
BASTU
Output:
ABABTU