题目描述

对于两个字符串$s_1$和$s_2$，定义$s_1$和$s_2$的"最小公倍串"$S$满足如下性质：

性质1、从串中选出一些字符按顺序排列，能构成$s_1$和$s_2$。

性质2、对于所有满足性质1的串，其长度最小

性质3、对于所有满足性质1和2的串，其字典序最小

现在给出两个字符串，请你求出它的最小公倍串。

输入格式

两行，每行一个字符串。

输出格式

一行一个字符串，代表最小公倍串。

输入输出样例 #1

输入 #1

abd
ce

输出 #1

abcde

输入输出样例 #2

输入 #1

abd
cbd

输出 #2

acbd

说明/提示

对20%的数据，两个字符串长度$<=10^2$。

对100%的数据，$1\leq$两个字符串长度$<=5\times 10^3$。