시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

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 kn+i = ai for i ≥ 1. Encryption of the plaintext a to the ciphertext b follows the formula bi = ai + ki mod 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.

입력

The input consists of:

  • One line with two integers n and m (1 ≤ n ≤ 30, n + 1 ≤ m ≤ 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 the plaintext of John’s diary.

예제 입력 1

5 16
again
pirpumsemoystoal

예제 출력 1

marywasnosyagain

예제 입력 2

1 12
d
fzvfkdocukfu

예제 출력 2

shortkeyword