F. Compromise
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A few days before the competition, the problem authors Slava and Tolya got into a heated argument.

Slava claimed that the string $$$S$$$ of length $$$n$$$ is the best title for the problem.

Tolya insisted that the best title for the problem is the string $$$T$$$ of length $$$n$$$.

To avoid ruining their friendship over some strings, the guys decided to find a string that would satisfy both of them.

They formulated the following criteria for the string—compromise $$$P$$$:

  • $$$P$$$ must also be of length $$$n$$$, just like the strings $$$S$$$ and $$$T$$$.
  • $$$P$$$ must be a palindrome (i.e., read the same forwards and backwards)—this way, both Slava and Tolya can read it simultaneously from both sides.
  • The total distance $$$d(S, P) + d(T, P)$$$ must be minimized (see note).

Help the guys—find the string $$$P$$$ that satisfies the conditions described above.

Input

The first line contains an integer $$$n$$$ $$$(1 \le n \le 5 \cdot 10^4)$$$—the length of the strings $$$S$$$ and $$$T$$$.

The second line contains the string $$$S$$$ $$$(|S| = n)$$$—the best title for the problem according to Slava.

The third line contains the string $$$T$$$ $$$(|T| = n)$$$—the best title for the problem according to Tolya.

It is guaranteed that the strings $$$S$$$ and $$$T$$$ consist only of lowercase Latin alphabet characters.

Output

In a single line, output the string $$$P$$$—the compromise string that satisfies the following conditions:

  • the length of $$$P$$$ is $$$n$$$;
  • $$$P$$$ consists only of lowercase Latin alphabet characters.
  • $$$P$$$ is a palindrome.
  • $$$d(S, P) + d(T, P)$$$ takes the minimum possible value.

If there are multiple strings $$$P$$$ that satisfy the conditions—output any.

Examples
Input
4
axcy
pbqd
Output
kmmk
Input
7
qwertyu
jhgfdsa
Output
oueieuo
Note

Palindrome—a string that reads the same forwards and backwards.

Examples of palindromes: tenet, abacaba, pqqp, d.

Distance $$$d(A, B)$$$ between strings $$$A$$$ and $$$B$$$ of the same length $$$n$$$ is calculated as $$$\sum{|A_i - B_i|}$$$, where $$$A_i - B_i$$$ is the difference in positions of characters $$$A_i$$$ and $$$B_i$$$ in the Latin alphabet.

First test example

The string $$$S$$$ is axcy.

The string $$$T$$$ is pbqd.

Examples of possible strings $$$P$$$: kmmk, oddo, eeee, and many others.

The total distance $$$d(S, P) + d(T, P)$$$ for $$$P$$$ = kmmk will be:

  • $$$d(S, P) = |a - k| + |x - m| + |c - m| + |y - k|$$$ = $$$|1 - 11| + |24 - 13| + |3 - 13| + |25 - 11| = 10 + 11 + 10 + 14 = 45$$$.
  • $$$d(T, P) = |p - k| + |b - m| + |q - m| + |d - k|$$$ = $$$|16 - 11| + |2 - 13| + |17 - 13| + |4 - 11| = 5 + 11 + 4 + 7 = 27$$$.
  • Accordingly, the total distance will be $$$45 + 27 = 72$$$.

It can be shown that $$$72$$$ is the minimum possible value for suitable strings $$$P$$$.