Shortest Shiritori

問題文

文字列 $S_1, S_2$ が与えられます。
$S_1 \to T \to S_2$ の順でしりとりが成立するような文字列 $T$ のうち、長さが最小のものを出力してください。

厳密には、次の条件を満たす文字列 $T$ のうち、長さが最小のものを出力してください。

• $S_1$ の末尾の文字と $T$ の先頭の文字が一致する。
• $T$ の末尾の文字と $S_2$ の先頭の文字が一致する。

制約

• $S_1, S_2$ は英小文字からなる長さ $1$ 以上 $10$ 以下の文字列

入力

入力は以下の形式で標準入力から与えられる。

出力

文字列 $T$ のうち、長さが最小のものを出力せよ。

サンプル1

abc
de

cd

abc $\to T \to$ de を満たす長さが最小の $T$ は cd です。

サンプル2

xyz
zoom

z

サンプル3

shiritori
gorilla

ig