Problem Description

Given a string $S$ of length $N$ that contains only lowercase letters, and $M$ lowercase letters $c_1, c_2, \cdots, c_M$. Now you need to insert all $M$ lowercase letters into the string $S$, and each lowercase letter can be inserted at any position.

What is the lexicographically smallest string you can obtain?

Input Format

The first line contains two integers $N$ and $M$.

The second line contains a string $S$ of length $N$.

The third line contains $M$ lowercase letters $c_1, c_2, \cdots, c_M$.

Output Format

Output a string of length $N + M$ as the answer.

4 3
abbc
cba

aabbbcc

7 3
lanqiao
bei

beilanqiao

Hint

【Test case scale and constraints】

For $20\%$ of the test cases, $M = 1$.

For $100\%$ of the test cases, $1 \le N, M \le 10^5$.

Translated by ChatGPT 5