P10910 [Lanquiao Cup 2024 National B] Minimum String

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?

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 a string of length $N + M$ as the answer.

**【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