Write Python code to solve the task:
You are given two strings s and t, both consisting of exactly k lowercase Latin letters, s is lexicographically less than t.

Let's consider list of all strings consisting of exactly k lowercase Latin letters, lexicographically not less than s and not greater than t (including s and t) in lexicographical order. For example, for k=2, s="az" and 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 s and not greater than t.

Input

The first line of the input contains one integer k (1 ≤ k ≤ 2 ⋅ 10^5) — the length of strings.

The second line of the input contains one string s consisting of exactly k lowercase Latin letters.

The third line of the input contains one string t consisting of exactly k lowercase Latin letters.

It is guaranteed that s is lexicographically less than t.

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

Output

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

Examples

Input


2
az
bf


Output


bc


Input


5
afogk
asdji


Output


alvuw


Input


6
nijfvj
tvqhwp


Output


qoztvz
user
Step 1: Input the length of strings 'k', string 's', and string 't'.
Step 2: Generate a list of all strings consisting of exactly 'k' lowercase Latin letters, lexicographically not less than 's' and not greater than 't' in lexicographical order.
Step 3: Find the index of the middle element of the list.
Step 4: Print the string at the middle index.

For example, if k=2, s="az", and t="bf", the list will be ["az", "ba", "bb", "bc", "bd", "be", "bf"]. The middle index is 3, so the median is "bc".
```python
# Step 5: Take input for the length of the strings 'k', string 's', and string 't'.


import sys

k = int(sys.stdin.readline())
s = sys.stdin.readline().rstrip()
t = sys.stdin.readline().rstrip()

# Step 6: Generate a list of all strings consisting of exactly 'k' lowercase Latin letters, lexicographically not less than 's' and not greater than 't' in lexicographical order.
string_list = []
count = 0
for i in range(k):
    if t[i] == s[i]:
        string_list.append(t[:i] + t[i])
        count += 1
    else:
        string_list.append(t[:i] + chr(ord(t[i])-1))
        count += 1
        break
for i in range(count, k):
    string_list.append(t[:i] + t[i])

# Step 7: Find the index of the middle element of the list.
median_index = len(string_list) // 2

# Step 8: Print the string at the middle index.
print(string_list[median_index])
```
assistant
Your answer is wrong.
The assistant's solution isn't correct and doesn't seem to follow the correct approach towards the problem solution. The approach they took to generate a list of all strings is wrong. They also didn't account the weight of each character based on their position, which is an essential part in finding the median string. It's important in this problem to understand that the strings implicitly define a large range of numbers, and we need to find the middle-number from that range and convert it back to string. It could be more beneficial to use the ASCII values of the characters to detect the mid-point. I would suggest rethinking their approach.
user
Step 1: Input the length of strings 'k', string 's', and string 't'.
Step 2: Convert the strings 's' and 't' into their ASCII values.
Step 3: Find the middle ASCII value between the ASCII values of 's' and 't'.
Step 4: Convert the middle ASCII value back to a string.
```python
# Step 5: Take input for the length of the strings 'k', string 's', and string 't'.
k = int(input())
s = input()
t = input()

# Step 6: Convert the strings 's' and 't' into their ASCII values.
s_ascii = [ord(c) for c in s]
t_ascii = [ord(c) for c in t]

# Step 7: Find the middle ASCII value between the ASCII values of 's' and 't'.
middle_ascii = [(s_ascii[i] + t_ascii[i]) // 2 for i in range(k)]

# Step 8: Convert the middle ASCII value back to a string.
middle_string = ''.join([chr(ascii_val) for ascii_val in middle_ascii])

# Step 9: Print the median string.
print(middle_string)
```
assistant
Your answer is wrong.
You are unfortunately still not approaching the problem correctly. Your step 7 does not correctly find the middle string. You are finding the average of the ascii values of the characters at the same index in strings 's' and 't'. This is not right because the average of two chars may not be a char. Also, your approach doesn't consider that we need to find the middle string in the lexicographical order that falls in the range between 's' and 't'. You need to understand that the problem can be seen as finding the median of a specific range in an arithmetic series. So think of the solution in terms of arithmetic median. I would suggest rethinking your approach.
user
Step 1: Input the length of strings 'k', string 's', and string 't'.
Step 2: Convert the strings 's' and 't' into their ASCII values.
Step 3: Find the arithmetic median of the ASCII values of 's' and 't'.
Step 4: Convert the arithmetic median back to a string.
```python
# Step 5: Take input for the length of the strings 'k', string 's', and string 't'.
k = int(input())
s = input()
t = input()

# Step 6: Convert the strings 's' and 't' into their ASCII values.
s_ascii = [ord(c) for c in s]
t_ascii = [ord(c) for c in t]

# Step 7: Find the arithmetic median of the ASCII values of 's' and 't'.
median_ascii = s_ascii.copy()
for i in range(k):
    if s_ascii[i] != t_ascii[i]:
        median_ascii[i] += (t_ascii[i] - s_ascii[i]) // 2

# Step 8: Convert the arithmetic median back to a string.
median_string = ''.join([chr(ascii_val) for ascii_val in median_ascii])

# Step 9: Print the median string.
print(median_string)
```
assistant
Your answer is wrong.
The logic in finding the arithmetic median of the ASCII values of 's' and 't' is incorrect, especially considering the different weights of each character based on its position within the string. ASCII values don't correlate exactly to a numeric representation of the string. The solution must understand that each character in a string holds a weighted value based on its position. You may benefit from a different approach that interprets the strings as numbers where each digit is a letter from 'a' to 'z' mapped to numbers from 0 to 25. Using this logic you should aim to find the difference between 't' and 's', half it and add it to 's' to get the median string. It's important to handle the possible carry while halving the difference. Such an approach doesn't require generating list of all possible strings, which would be inefficient.  Please, reconsider and develop a solution accordingly.
user
Step 1: Input the length of strings 'k', string 's', and string 't'.
Step 2: Create a mapping from 'a' to 'z' to their corresponding numeric values from 0 to 25.
Step 3: Convert the strings 's' and 't' into a list of their numeric values.
Step 4: Find the difference between the numeric values of 't' and 's'.
Step 5: Halve the difference and add it to the numeric values of 's' to get the numeric values of the median string.
Step 6: Handle any carry while adding.
Step 7: Convert the numeric values back to characters using the mapping.
Step 8: Print the median string.
```python
# Step 9: Take input for the length of the strings 'k', string 's', and string 't'.
k = int(input())
s = input()
t = input()

# Step 10:  Create a mapping from 'a' to 'z' to their corresponding numeric values from 0 to 25.
char_to_num = {chr(ord('a')+i): i for i in range(26)}

# Step 11:  Convert the strings 's' and 't' into a list of their numeric values.
s_nums = [char_to_num[c] for c in s]
t_nums = [char_to_num[c] for c in t]

# Step 12:  Find the difference between the numeric values of 't' and 's'.
diff = [t_nums[i] - s_nums[i] for i in range(k)]

# Step 13:  Halve the difference and add it to the numeric values of 's' to get the numeric values of the median string.
median_nums = [s_nums[i] + diff[i] // 2 for i in range(k)]

# Step 14:  Handle any carry while adding.
for i in range(k-1, -1, -1):
    if median_nums[i] > 25:
        median_nums[i] %= 26
        median_nums[i-1] += 1

# Step 15:  Convert the numeric values back to characters using the mapping.
num_to_char = {i: chr(ord('a')+i) for i in range(26)}
median = ''.join([num_to_char[num] for num in median_nums])

# Step 16:  Print the median string.
print(median)
```
assistant
Your answer is wrong.
You have 1 steps left and 1 chances to propose solution left.
Your approach to finding the arithmetic median of the numeric values of 's' and 't' is incorrect because you simply halved the difference and added it to 's'. This does not consider the weights of individual characters, that is, not every character contributes equally to the overall lexicographical value of the string. The mapping of characters to numbers doesn't hold the actual weights for each character based on its position in the string. Plus, simply halving the difference and adding it to s_nums does not ensure the resulting median_nums falls in the range [s_nums, t_nums]. Your handling of carry was correct but in the wrong context. I advice you to consider using a whole string "s" or "t" as an integral number, we can interpret each string as a large number where each digit is a letter from 'a' to 'z' mapped to numbers from 0 to 25. The solution requires finding the sum of "s" and "t" as numbers and then halve it taking into account the carry, then map it back to strings. This accomplishes an implicit check on the median value falling into the range [s, t].
user
Step 1: Parse the input to get the length of the strings 'k', and strings 's' and 't'. 
Step 2: Convert the strings 's' and 't' into their equivalent base 26 numbers 's_num' and 't_num'
Step 3: Find the sum of 's_num' and 't_num'.
Step 4: Divide the sum by 2 to get the median.
Step 5: Convert the median back to a base-26 string considering the carries.
Step 6: Print the median string.
```python
# Step 7: Parse the input to get the length of the strings 'k', and strings 's' and 't'.
k = int(input())
s = input()
t = input()

# Step 8: Convert the strings 's' and 't' into their equivalent base 26 numbers 's_num' and 't_num'
s_num = 0
t_num = 0
for i in range(k):
    s_num = s_num * 26 + (ord(s[i]) - ord('a'))
    t_num = t_num * 26 + (ord(t[i]) - ord('a'))

# Step 9: Find the sum of 's_num' and 't_num'.
sum_num = s_num + t_num

# Step 10: Divide the sum by 2 to get the median.
median_num = sum_num // 2

# Step 11: Convert the median back to a base-26 string considering the carries.
median_string = ""
while median_num > 0:
    median_string = chr(ord('a') + (median_num % 26)) + median_string
    median_num //= 26

median_string = median_string.rjust(k, 'a') # pad with 'a' if necessary

# Step 12: Print the median string.
print(median_string)
```
assistant