P10244 String Minimization

You are given four strings $a, b, c, d$, each of length $n$. You may perform the following operation any number of times: - Choose an index $i$, swap $a_i$ and $c_i$, then swap $b_i$ and $d_i$. Find the lexicographically smallest possible string $b$, under the condition that the resulting string $a$ is as lexicographically small as possible. --- If you do not know what lexicographical order is, see below: For two strings $p, q$, we say $p$ is lexicographically smaller than $q$ (written as $p

The first line contains a positive integer $n$, the length of strings $a, b, c, d$. The next four lines each contain a string, representing $a, b, c, d$ respectively.

Output one line containing a string, the required string $b$.

[Sample Explanation] Choosing $i$ as $1, 3, 4$ can make $a$ reach the minimum lexicographical order $\texttt{weablake}$. At this time, string $b$ also becomes the minimum lexicographical order that satisfies the requirement, which is $\texttt{auazyqaq}$. In fact, if we do not operate when $i=1$, the lexicographical order of $a$ is still minimal, but then string $b$ would be $\texttt{yuazyqaq}$, which is not small enough. [Constraints] This problem has $10$ test points, each worth $10$ points. |Test Point ID|$n\le$|Special Property| |:-:|:-:|:-:| |$1\sim 2$|$15$|| |$3$|$10^5$|$a_i>c_i$| |$4\sim 5$|$10^5$|$a_i\ne c_i$| |$6\sim 7$|$10^5$|$b_i\ge d_i$| |$8\sim 10$|$10^5$|| For all testdata, it is guaranteed that $1\le n\le 10^5$, and all characters in the strings are lowercase letters. Translated by ChatGPT 5