题目描述

给定一个长度为$N$且只包含小写字母的字符串$S$，和$M$个小写字母$c_1,c_2,...,c_M$。现在你要把$M$个小写字母全部插入到字符串$S$中，每个小写字母都可以插入到任意位置。

请问能得到的字典序最小的字符串是什么？

输入格式

第一行包含两个整数$N(1 \leq N \leq 10^5)$和$M(1 \leq M \leq 10^5)$。

第二行包含一个长度为$N$的字符串$S$，保证只包含小写字母。

第三行包含M个小写字母$c_1,c_2,...,c_M$。

输出格式

输出一个长度为$N + M$的字符串代表答案。

样例

4 3
abbc
cba

aabbbcc

提示

2024年蓝桥杯B组国赛E题。