 Code Submission Evaluation System Login

HIIT Open 2017

 Start: 2017-05-27 11:00:00 End: 2017-05-27 16:00:00

CSES - HIIT Open 2017 - Median stringCSES - Median string

Median string

 Time limit: 1.00 s Memory limit: 512 MB

Let $d(a,b)$ denote the edit distance between strings $a$ and $b$, which is the minimum number of editing operations needed to transform $a$ into $b$. The allowed editing operations are as follows:
• remove one character
• change one character
For example, $d(\texttt{AABA},\texttt{CAA})=2$, because we can remove the $\texttt{B}$ letter and change the first $\texttt{A}$ letter.

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$
Example

Input:
ABBA AYBABTU BASTU

Output:
ABABTU