Search for the minimum window containing all characters from the pattern string

C# Hard strings

Task «Search for the minimum window containing all characters from the pattern string»

Given two strings: s and t. It is necessary to find the minimum substring (window) in s that contains all characters from t (including repetitions). If such a window does not exist, output an empty string. It is guaranteed that the strings consist of lowercase Latin letters. String lengths: 1 ≤ |s|, |t| ≤ 10^5.

Input Format

On the first line — string s. On the second line — string t.

Output Format

One line — the desired minimum substring, or an empty line if there is no solution.

Examples

Example 1

INPUT

ADOBECODEBANC
ABC

OUTPUT

BANC

Example 2

INPUT

a
b

OUTPUT

main.cs