Description:

As you studied in the subject "Dynamic Programming" you can program a variant of the Edit Distance algorithm, to implement a Longest Common Subsequence algorithm.

In this problem, you will have to implement a Longest Common Subsequence algorithm.

Input

The input comes in two lines, in the first line, you will have a string s, in the second line you will have a string t.

Output

You will have to inform the longest scattered string of characters which is included within both words (s and t).

Example

Input:
Argentina
gienote


Output:
gent