Олимпиадный тренинг

Задача . E. Медианная строка


Заданы две строки \(s\) и \(t\), обе состоят ровно из \(k\) строчных букв латинского алфавита, \(s\) лексикографически меньше \(t\).

Рассмотрим список всех строк, состоящих ровно из \(k\) строчных латинских букв, лексикографически не меньших, чем \(s\) и не больше, чем \(t\) (включая \(s\) и \(t\)) в лексикографическом порядке. Например, для \(k=2\), \(s=\)«az» и \(t=\)«bf» список будет равен [«az», «ba», «bb», «bc», «bd», «be», «bf»].

Ваша задача — вывести медиану (средний элемент) этого списка. Для примера выше это будет «bc».

Гарантируется, что количество строк, лексикографически не меньших, чем \(s\) и не больших, чем \(t\), нечетно.

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

Первая строка входных данных содержит одно целое число \(k\) (\(1 \le k \le 2 \cdot 10^5\)) — длину строк.

Вторая строка входных данных содержит строку \(s\), состоящую ровно из \(k\) строчных букв латинского алфавита.

Третья строка входных данных содержит строку \(t\), состоящую ровно из \(k\) строчных букв латинского алфавита.

Гарантируется, что \(s\) лексикографически меньше \(t\).

Гарантируется, что количество строк, лексикографически не меньших, чем \(s\) и не больших, чем \(t\), нечетно.

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

Выведите одну строку, состоящую ровно из \(k\) строчных букв латинского алфавита — медиану (средний элемент) списка строк длины \(k\), лексикографически не меньших, чем \(s\) и не больших, чем \(t\).


Примеры
№Входные данныеВыходные данные
1
2
az
bf
bc
2
5
afogk
asdji
alvuw
3
6
nijfvj
tvqhwp
qoztvz
Статистика успешных решений по компиляторам
 Кол-во
С++5