Smallest Window Substring

Given two strings s1 and s2, your task is to find the smallest contiguous substring (window) in s1 that contains all the characters of s2 including duplicates. If no such window exists, output an empty string.

The problem can be mathematically described as follows: Given a string \( S_1 \) of length \( n \) and a string \( S_2 \) of length \( m \) (with \( m \leq n \)), find the minimum index pair \( (l, r) \) such that all characters in \( S_2 \) (with their multiplicities) are contained in \( S_1[l\ldots r] \). If there is no such pair, return an empty string.

Example:

Input:
ADOBECODEBANC
ABC
Output:
BANC

</p>

inputFormat

The input is read from stdin and consists of two lines:

1. The first line contains the string s1.
2. The second line contains the string s2.

Both strings will consist of uppercase/lowercase letters.

outputFormat

Print to stdout the smallest window in s1 that contains all characters of s2 (including duplicates). If there is no valid window, output an empty string.

## sample

ADOBECODEBANC
ABC

BANC