21984_Littera

Littera is an encryption system used in ancient Russian manuscripts. Several variations of littera are known, and we investigate one used on the Latin alphabet.

The plaintext is encrypted using a short keyword consisting of lowercase Latin letters. Only Latin letters are replaced during the encryption, all other symbols remain unchanged. The letters are divided into blocks so that all (except for the last one, possibly) have the same length as the key. If a1 is the position of the first letter of the plaintext in the alphabet and b1 is the position of the first letter of the key, then the first letter of the text is replaced with the letter on the position a₁+b₁ of the alphabet (if a₁+b₁ > 26, the letter a₁+b₁-26 is used instead). The case of the letters of the plaintext is preserved. The following letters of each block are encrypted in the same manner , using the corresponding letter of the key.

For example, let the plaintext be "crusader" and the key "bow". Then the first letter of the ciphertext is 'e' (the position of the first letter of the plaintext is 3 and the position of the first letter of the key is 2, thus the first letter of the ciphertext must be from the position 5 of the alphabet). The second letter of the plaintext is replaced with 'g' (18+15=33, 33-26=7). Continuing in the same manner , the whole ciphertext turns out to be "egrupagg". Note that in this case each letter of the plaintext is always represented by the same letter in the ciphertext, but this is a mere coincidence -- it does not happen when the distance between the occurrences of a letter in the plaintext is not a multiple of the length of the key!

You are given two fragments of a document: one in plaintext, the other encrypted using the above system. The lengths of the fragments are equal and it is known that the first character of the ciphertext is obtained from the first character of the plaintext. It is also known that the number of letters in the given fragments is no less than the length of the keyword. It is, however , not known whether the fragments start at the beginning of a document!

Based on the given data, derive the shortest possible keyword!

The first line of the input contains N (1 ≤ N ≤ 10⁶) -- the number of characters in each fragment. It is followed by the two text fragments, first the plaintext and then the ciphertext. The ciphertext always starts from a new line, but each of the fragments may be arbitrarily split across several lines.

The first and only line of the output should contain the keyword. If there are several possible keywords, output the one earliest in the lexicographic order.

8
Crusader
Egrupagg

bow