Problem D
Kleptography
John likes simple ciphers. He had been using the “Caesar” cipher to encrypt his diary until recently, when he learned a hard lesson about its strength by catching his sister Mary browsing through the diary without any problems.
Rapidly searching for an alternative, John found a solution: the famous “Autokey” cipher. He uses a version that takes the $26$ lower-case letters ‘a’–‘z’ and internally translates them in alphabetical order to the numbers $0$ to $25$.
The encryption key $k$ begins with a secret prefix of $n$ letters. Each of the remaining letters of the key is copied from the letters of the plaintext $a$, so that $k_{n+i} = a_{i}$ for $i \geq 1$. Encryption of the plaintext $a$ to the ciphertext $b$ follows the formula $b_ i = a_ i + k_ i \bmod 26$.
Mary is not easily discouraged. She was able to get a peek at the last $n$ letters John typed into his diary on the family computer before he noticed her, quickly encrypted the text document with a click, and left. This could be her chance.
Input
The input consists of:
-
One line with two integers $n$ and $m$ ($1 \le n \le 30$, $n + 1 \le m \le 100$), where $n$ is the length of the keyword as well as the number of letters Mary saw, and $m$ is the length of the text.
-
One line with $n$ lower-case letters, the last $n$ letters of the plaintext.
-
One line with $m$ lower-case letters, the whole ciphertext.
Output
Output the plaintext of John’s diary.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 16 again pirpumsemoystoal |
marywasnosyagain |
| Sample Input 2 | Sample Output 2 |
|---|---|
1 12 d fzvfkdocukfu |
shortkeyword |
