406680: GYM102483 K Kleptography

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

K. Kleptographytime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

ExamplesInput
5 16
again
pirpumsemoystoal
Output
marywasnosyagain
Input
1 12
d
fzvfkdocukfu
Output
shortkeyword

加入题单

上一题 下一题 算法标签: