Problem Background

English statement. You must submit your code at the Chinese version of the statement.

You can cry

Drinking your eyes

Do you miss the sadness when it's gone

And you let the river run wild

And you let the river run wild

— The River by AURORA

Problem Description

Autumn has two strings \(a\) and \(b\) of length \(n\) each, consisting only of # and lowercase letters.

These two strings together contain \(m\) # characters. Autumn plans to perform \(m\) operations to replace all # characters in both strings with lowercase letters. For the \(i\)-th operation, he will choose one of the strings \(a\) or \(b\), and replace the first # from the left in that string with the \((i-1) \bmod 26 + 1\)-th lowercase letter. He cannot choose a string that does not contain #.

Autumn has a friend who loves art, and he wants to minimize the lexicographical order of string \(a\) after \(m\) operations. Autumn thinks that programming is also an art, and this way, their hearts will be closer.

Input Format

The first line contains two positive integers \(n\) and \(m\).

The second line contains a string \(a\) of length \(n\).

The third line contains a string \(b\) of length \(n\).

Output Format

Output a single line containing the string \(a\) after \(m\) operations, which has the smallest possible lexicographical order.

Sample Input and Output

Sample Input #1

8 2
th#nkyou
#estwish

Sample Output #1

thankyou

Sample Input #2

16 5
##soluteradian#e
your#awnwillcom#

Sample Output #2

absoluteradiance

Sample Input #3

40 45
hhuj#pzr#k#mmd#z##y#o####m##j##tga#k#t#g
m########be#######vf##a#j###ypuf###pr###

Sample Output #3

hhujapzrakbmmdczdeyfoghijmkljmntgaokptqg

Notes

「Sample Explanation #1」

For the first operation, choose string \(a\) and replace the # with the \((1-1) \bmod 26+1=1\)-th lowercase letter, which is a. For the second operation, choose string \(b\) and replace the # with the \((2-1) \bmod 26+1=2\)-th lowercase letter, which is b. The final string \(a\) is thankyou, and it can be proven that this is the smallest lexicographical order achievable after \(m\) operations.

「Data Range」

• Special Property: One of the strings \(a\) or \(b\) is guaranteed to not contain #.

For all test data, \(1 \leq n \leq 10^5\), \(1 \leq m \leq 2n\), and strings \(a\) and \(b\) consist only of characters # and lowercase letters.

August 4, 2024: Added 1 set of hack data in Subtask #1.

见题面 Input 部分

见题面 Output 部分