EDITV1 - Edit Distance Variant 1

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

Added by:Coach UTN FRSF
Date:2011-07-18
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.