SDE Path

Minimum Window Subsequence

Hard

Minimum Window Subsequence

Find the smallest contiguous window in one string containing another string as a subsequence.

Input format

The first line contains string S. The second line contains string T (|S| ≤ 25, |T| ≤ 5).

Output format

Print the smallest window in S that contains T as a subsequence. If multiple windows of the same length exist, return the leftmost. If none exist, return -1.

Constraints

  • Values fit in a 64-bit signed integer
  • Trailing whitespace and a trailing newline are ignored by the judge

Read from stdin, write to stdout. Sample cases below show the exact format.

Sample cases

Example 1
Input
abcdefg acg
Expected output
abcdefg
Example 2
Input
a a
Expected output
a