Minimum Window Substring

You are given two strings S1 and S2. Your task is to find the smallest contiguous substring (window) in S1 that contains all the characters in S2 (including multiplicity). If no such window exists, output an empty string. If there are multiple such windows, output the one that appears first in S1.

The solution should be efficient. A common approach is to use the sliding window technique with a time complexity near O(n), where n is the length of S1.

Note: The matching is case-sensitive.

Mathematical Formulation:

Let S1 be a string and S2 be a multiset of characters. Find indices l and r such that:

\[ \{S1[l..r]\} \supseteq S2 \]

and r - l + 1 is minimized.

inputFormat

The input consists of two lines. The first line contains the string S1 and the second line contains the string S2.

outputFormat

Output the smallest substring of S1 that contains all the characters of S2. If no such substring exists, print an empty string.

## sample

ADOBECODEBANC
ABC

BANC