Minimum Window Substring

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

Constraints

• m == s.length, 1 ≤ m ≤ 105
• n == t.length, 1 ≤ n ≤ 105
• s and t consist of uppercase and lowercase English letters.

Examples

Input:  s="ADOBECODEBANC", t="ABC"  -> "BANC"
Input:  s="a", t="a"               -> "a"
Input:  s="a", t="aa"              -> "" (only one 'a' in s)