← 返回题目列表

Codeforces · 1144/E

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

输出 #1

bc

输入 #2

5
afogk
asdji

输出 #2

alvuw

输入 #3

6
nijfvj
tvqhwp

输出 #3

qoztvz