Problem Description

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<q$) if and only if there exists a non-negative integer $k$ such that the first $k$ characters of $p$ and $q$ are the same, and the ASCII code of $p_{k+1}$ is smaller than that of $q_{k+1}$.

For example:

• $\texttt{abc}<\texttt{baa}$ (when $k=0$)
• $\texttt{bae}<\texttt{bbb}$ (when $k=1$).

Input Format

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 Format

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

8
westlake
yummyqaq
weabzzke
azazazaq

auazyqaq

Hint

[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.

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