题目背景

Y 同学正在进行一项基因序列的匹配研究。他有一个长长的基因文本串 $S$ 和一个较短的模式串 $T$。他需要从 $S$ 中找到一个最短的连续片段，这个片段能够“覆盖”模式串 $T$ 中所有的碱基种类和数量。

题目描述

给定一个源字符串 $S$ 和一个目标字符串 $T$。

你需要从 $S$ 中找出一个连续子串，这个子串必须包含 $T$ 中所有的字符，并且满足 $T$ 中每个字符的出现次数要求。

形式化地说，如果 $T$ 中字符 c 出现了 $k$ 次，那么你找到的 $S$ 的子串中，字符 c 的出现次数必须不少于 $k$ 次。

请你在所有满足上述条件的子串中，找出长度最小的一个。如果不存在这样的子串，则返回一个空字符串 ""。

题目保证，如果存在答案，这个最小长度的子串是唯一的。

输入格式

第一行包含一个字符串 $S$。 第二行包含一个字符串 $T$。

输出格式

输出一行，一个字符串，表示满足条件的最小覆盖子串。如果不存在，则输出一个空行。

样例

样例输入 #1

ADOBECODEBANC
ABC

样例输出 #1

BANC

样例输入 #2

a
a

样例输出 #2

a

样例输入 #3

a
aa

样例输出 #3

(空行)

提示

样例解释

• 样例 1: 目标串 $T$ 为 "ABC"。源串 $S$ 中，子串 "BANC" 包含了 'A', 'B', 'C' 各一个，满足条件。其长度为 4，是所有满足条件的子串中最短的。

• 样例 2: 目标串 $T$ 为 "a"。源串 $S$ 本身就是满足条件的最小子串。

• 样例 3: 目标串 $T$ 为 "aa"，需要两个 'a'。源串 $S$ 中只有一个 'a'，无法满足条件，因此不存在覆盖子串。

数据范围与约定

• $|S|$ 和 $|T|$ 分别表示字符串 $S$ 和 $T$ 的长度。
• $1 \le |S|, |T| \le 10^5$
• $S$ 和 $T$ 仅由大小写英文字母构成。