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 b 1 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 a1+b1
of the alphabet (if a1+b1 > 26, the letter a1+b1-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 ≤ 106) –
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. In the example below, the newlines are marked with the character ’•’ which
will not be present in the actual input files.
If a line begins with a number digit, then it must be a beginning of a new test case.
each line should contain
the keyword. If there are several possible keywords, output the one earliest in the
lexicographic order .
8 Crusader Egrupagg 41 To be or not t o be? What is the question! Yp ru aw oej ft cu? Mtfu yi fmf gkqxuyez!
bow apple
Migrated from old NTUJ.
icpc2008, neerc west
| No. | Testdata Range | Score |
|---|