Calculate Score

Choose a non-empty substring t of text. The prefix score is the longest length by which a prefix of t matches a suffix of prefixString; the suffix score is the longest length by which a suffix of t matches a prefix of suffixString. The total score is their sum, and the two matches may overlap; on a tie for the highest score, choose the lexicographically smallest t.

输入格式

Three lines: text, prefixString, and suffixString, in that order; each has length 1..50 and contains only lowercase letters; text is guaranteed to match at least one character on at least one side.

输出格式

Output the lexicographically smallest non-empty substring with the highest score.

样例 1

输入：

engine
raven
ginkgo

输出：

engin

样例 2

输入：

banana
bana
nana

输出：

banana

样例 3

输入：

ab
b
a

输出：

a

样例说明

The outputs of the three public examples are, in order: engin; banana; a. These answers were verified by independent enumeration or direct simulation.