Python言語で提出する際の諸注意

• この問題においてPython言語で解く際は、必ず入力の後に strip 関数を適用してください。
  つまり入力の際に S = input().strip() と書いてください（でないとジャッジの環境上、WAになる可能性が高いです）

Story

🐤

新年度もやっぱり $\text{Scottish Fold}$ さん（※フィクションです）を見ないと、今年を生きている感じがしません。

ところで $\text{Fold}$ とは日本語で「折りたたむ」という意味を持っています。
なので、$\text{Fold}$ という文字列をじゃばら折りとして折りたたんで、先頭と末尾の文字を除いてみてみましょう。

ぐしゃっ

お、$\text{Fd}$ になりましたね。ちょっと楽しいですねこれ^^。
これをシミュレーションしてみましょう。

問題

文字列 $S,T$ が与えられます。次のいずれの条件を満たすような文字列 $X$ を求めてください。

• $S$ に対する任意の長さ $3$ 以上の連続部分文字列 $X$ において、$X$ の先頭および末尾の文字を除いた文字列を $A$ とする。
• $T$ において連続する $2$ 文字の間に $A$ を順序を保ったまま挿入することで、挿入後に $T=S$ を満たすような挿入方法が少なくとも一つ存在する。

厳密には、$S$ に対する $l$ 文字目から $r$ 文字目までの連続部分文字列 $X=S_lS_{l+1}\dots S_{r-1}S_{r}$ とすると、$A=S_{l+1}S_{l+2}\dots S_{r-2}S_{r-1}$ となります。
そして $T$ の $a\ (1\le a\le |T|-1)$ 文字目と $a+1$ 文字目の間に $A$ を挿入すると、挿入後は $T'=T_1T_2\dots T_a \bm{S_{l+1}S_{l+2}\dots S_{r-1}} T_{a+1}\dots T_{|T|}$ となります。
このとき $T'$ が $S$ に一致するような $X$ を求めてください。

なお本問題の制約下で、答えとなる $X$ は一意に定まることが保証されます。

$|S|$ とは

文字列 $S$ に対して、$|S|$ は $S$ の長さを表します。

入力

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

制約

• $2\le |T|\lt |S|\le 500$
• $2\le |S|-|T|$
• 答えは一意に定まる
• 文字列は英小文字からなる

出力

答えとなる $X$ を出力せよ。

入出力例

scottishfold
scottishfd

fold

$X=$ fold とすると、$A=$ ol となります。ここで $T$ の $9,10$ 文字目の $2$ 文字の間に $A$ を挿入することで $S$ に一致することができます。
他にも候補となる $X$ はありますが、それらについては問題の条件を満たすような挿入方法は存在しません。

abba
aa

abba

$X=S$ であることがあります。

matcharate
matcrate

char