CSES - HIIT Open 2017 - 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:

  • add one character
  • 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