Median String

You are given two strings ss and tt, both consisting of exactly kk lowercase Latin letters, ss is lexicographically less than tt.

Let's consider list of all strings consisting of exactly kk lowercase Latin letters, lexicographically not less than ss and not greater than tt (including ss and tt) in lexicographical order. For example, for k=2k=2, s=s="az" and t=t="bf" the list will be ["az", "ba", "bb", "bc", "bd", "be", "bf"].

Your task is to print the median (the middle element) of this list. For the example above this will be "bc".

It is guaranteed that there is an odd number of strings lexicographically not less than ss and not greater than tt.

Input

The first line of the input contains one integer kk (1≤k≤2⋅1051≤k≤2⋅105) — the length of strings.

The second line of the input contains one string ss consisting of exactly kk lowercase Latin letters.

The third line of the input contains one string tt consisting of exactly kk lowercase Latin letters.

It is guaranteed that ss is lexicographically less than tt.

It is guaranteed that there is an odd number of strings lexicographically not less than ss and not greater than tt.

Output

Print one string consisting exactly of kk lowercase Latin letters — the median (the middle element) of list of strings of length kk lexicographically not less than ss and not greater than tt.

Examples

2
az
bf

bc

5
afogk
asdji

alvuw

6
nijfvj
tvqhwp

qoztvz

题意：给你两个只含有小写字母的字符串， s和t，保证s的字典序比t小。把s和t看成一个26进制的数，让你输出这两个数的中位数。
思路：首先把两个字符串的每一个位上的数值加起来，然后向前进位（从尾部开始）。
然后从头开始遍历加起来的那个数值，如果数值为偶数，那么中位数的这一位就是数值/2，如果是奇数，那么中位数的这一位是/2且向下取整。
并把那个多余的一加到下一位中，（注意上一位的1到下一位是26）。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<algorithm>
 7 using namespace std;
 8 int main()
 9 {
10 int n;
11 char str1[200005],str2[200005];
12 int a[200005];
13 scanf("%d",&n);
14 cin.get();
15 scanf("%s",str1);
16 cin.get();
17 scanf("%s",str2);
18 int flag=0;
19 for(int i=n-1;i>=0;i--)
20     {
21         int sum=str1[i]-'a'+str2[i]-'a'+flag;//flag做标记，进行满26进一
22         if(sum>=26&&i!=0)//第一位不用进一，到时候直接除以二就行
23         {
24             flag=1;
25             a[i]=sum-26;
26         }
27         else {
28            flag=0;
29            a[i]=sum;
30         }
31     }
32     for(int i=0;i<n;i++)
33         if(a[i]%2)
34     {
35         a[i+1]=a[i+1]+26;
36         a[i]/=2;
37     }
38     else
39         a[i]/=2;
40     for(int i=0;i<n;i++)
41         printf("%c",a[i]+'a');
42     printf("\n");
43     return  0;
44 }