Given two strings $S$ and $T$, please find the longest common substring of them. For your information, you could try to learn suffix automaton here, which could the problem in $O(|S| + |T|)$ time.

Input

The first line of the input contains the string $S$.
The second line of the input contains the string $T$.

Output

Please output The longest common substring.

Constraints

$1 \le |S|, |T| \le 10^6$