Given two strings, str1 and str2, return the smallest substring of str1 that contains every character from str2 (including duplicates). If no such substring exists, return an empty string.

A substring is any contiguous sequence of characters within a string. For example, the substrings of string abc are a, b, c, ab, bc, and abc. A substring is formed by selecting a starting and ending point without skipping characters in between.

Input

• str1: A string
• str2: A string

Notes

• If multiple solutions exist, you may return any of them

Input: str1 = "ABCD", str2 = "AC"
Output: "ABC"
Explanation: The substring 'ABC' contains both 'A' and 'C'

Input: str1 = "AAABBBCCC", str2 = "ABC"
Output: "ABBBC"
Explanation: The substring 'ABBBC' contains 'A', 'B', and 'C', making it the smallest valid substring.

Input: str1 = "A", str2 = "AA"
Output: ""
Explanation: str1 does not have enough 'A's to match the two required in str2, so the result is an empty string.

Constraints

• 1 <= str1.length, str2.length <= 10,000
• str1 and str2 contains only uppercase English letters