Problem Background

Mirko and Slavko are bored with their skiing trip, so they've started playing a new game.

Problem Description

Initially, Mirko specifies an integer $N$, and then Slavko writes down $N$ letters. Mirko writes a word of length $N$. Slavko needs to form a word from the $N$ letters he wrote, ensuring that no letter in his word matches the corresponding letter in Mirko's word at the same position. To make the game challenging, Mirko requires that Slavko's word is the lexicographically smallest among all valid words. Such a word will always exist. Given that Mirko and Slavko are young and only know the letters a, b, and c, the words they write will only contain these letters.

Help Slavko find such a word.

Input Format

The first line contains an integer $N$, representing the number of letters in the words written by Mirko and Slavko.
The second line contains a string of length $N$, representing the letters written by Slavko.
The third line contains a string of length $N$, representing the word written by Mirko.

Output Format

Output a single line containing a string of length $N$, representing the lexicographically smallest valid string.

For two strings $a$ and $b$ of length $N$, $a$ is lexicographically smaller than $b$ if and only if there exists an integer $p \in [1, N]$ such that $\forall i \in [1, p)$, $a_i = b_i$, and $a_p < b_p$.

Sample Input and Output

Sample Input #1

3
abc
abc

Sample Output #1

bca

Sample Input #2

4
baba
baab

Sample Output #2

abba

Sample Input #3

5
aaabc
abcba

Sample Output #3

baaac

Notes

[Data Range]

For $40\%$ of the test cases, $1 \leqslant N \leqslant 20$.
For all test cases, $1 \leqslant N \leqslant 5000$, and all strings contain only the letters a, b, and c.

[Problem Source]

This problem is from COCI 2016-2017 CONTEST 7 T3 IGRA, configured with the original problem data, worth $100$ points.

Provided by Eason_AC for translation and arrangement.

见题面 Input 部分

见题面 Output 部分