F. Компромисс
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

За несколько дней до соревнования авторы задач Слава и Толя вступили в жаркий спор.

Слава утверждал, что строка $$$S$$$ длины $$$n$$$ является самым лучшим названием для задачи.

Толя же настаивал, что самым лучшим названием для задачи является строка $$$T$$$ длины $$$n$$$.

Чтобы не разрушать дружбу из-за каких-то строчек, ребята решили найти строку, которая будет удовлетворять их обоих.

Они сформулировали следующие критерии для строки-компромисса $$$P$$$:

  • $$$P$$$ должна также быть длины $$$n$$$, как и строки $$$S$$$ и $$$T$$$.
  • $$$P$$$ обязана быть палиндромом (т.е. читаться одинаково слева-направо и справа-налево) — таким образом и Слава, и Толя смогут читать её одновременно с двух сторон.
  • Суммарное расстояние $$$d(S, P) + d(T, P)$$$ должно быть минимально возможным (см. примечание).

Помогите ребятам — найдите строку $$$P$$$, которая удовлетворяет описанным выше условиям.

Входные данные

В первой строке дано целое число $$$n$$$ $$$(1 \le n \le 5 \cdot 10^4)$$$ — длина строк $$$S$$$ и $$$T$$$.

Во второй строке дана строка $$$S$$$ $$$(|S| = n)$$$ — лучшее название для задачи по мнению Славы.

В третьей строке дана строка $$$T$$$ $$$(|T| = n)$$$ — лучшее название для задачи по мнению Толи.

Гарантируется, что строки $$$S$$$ и $$$T$$$ состоят только из символов латинского алфавита в нижнем регистре.

Выходные данные

В единственной строке выведите строку $$$P$$$ — строку-компромисс, удовлетворяющую следующим условиям:

  • длина $$$P$$$ равна $$$n$$$;
  • $$$P$$$ состоит только из символов латинского алфавита в нижнем регистре.
  • $$$P$$$ является палиндромом.
  • $$$d(S, P) + d(T, P)$$$ принимает минимально возможное значение.

Если существует несколько строк $$$P$$$, удовлетворяющих условиям — выведите любую.

Примеры
Входные данные
4
axcy
pbqd
Выходные данные
kmmk
Входные данные
7
qwertyu
jhgfdsa
Выходные данные
oueieuo
Примечание

Палиндром — строка, читающаяся одинаково слева направо и справа налево.

Примеры палиндромов: tenet, abacaba, pqqp, d.

Расстояние $$$d(A, B)$$$ между строками $$$A$$$ и $$$B$$$ одинаковой длины $$$n$$$ вычисляется как $$$\sum{|A_i - B_i|}$$$, где $$$A_i - B_i$$$ равно разнице позиций символов $$$A_i$$$ и $$$B_i$$$ в латинском алфавите.

Первый тестовый пример

Строка $$$S$$$ равна axcy.

Строка $$$T$$$ равна pbqd.

Примеры возможных строк $$$P$$$: kmmk, oddo, eeee и множество других.

Суммарное расстояние $$$d(S, P) + d(T, P)$$$ для $$$P$$$ = kmmk будет равно:

  • $$$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$$$ .
  • Соответственно, суммарное расстояние будет равно $$$45 + 27 = 72$$$.

Можно показать, что $$$72$$$ — минимально возможное значение для подходящих под условие строк $$$P$$$.