Minimum Window Substring

Given two strings S and T, find the smallest window (substring) in S that contains all the characters of T (including duplicates). If there is no such window, return an empty string. In case there are multiple windows of the same minimum length, return the one that appears first in S.

Formally, let S be a string of length n and T be a string of length m. We require a substring W = S[i..j] (with j - i + 1 = \ell) such that for every character \( c \), the number of occurrences of \( c \) in W is at least the number of occurrences of \( c \) in T.

Examples:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"
Input: S = "a", T = "a"
Output: "a"
Input: S = "a", T = "b"
Output: ""

</p>

inputFormat

The input is read from stdin and consists of two lines. The first line contains the string S, and the second line contains the string T. Both strings consist of uppercase and lowercase English letters.

outputFormat

Output a single line to stdout containing the smallest substring of S that contains every character in T. If no such substring exists, output an empty string.

## sample

ADOBECODEBANC
ABC

BANC