Description:

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

In this problem, you will have to implement a Substring Matching 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 best coincidence for the string s (a short string with length no longer than 18 characters), within a long text t (a longer text, up to 200 characters).

Example

Input:
Skienna
I think the author was Skina, I don't remember, Skinna or Skena


Output:
Skinna