Encryptastrophy

Time limit1sMemory limit2048 MB

Summary

Given a ciphertext where each letter is the mod 26 sum of a plaintext letter and the plaintext letter before it, plus the last plaintext letter, recover the full plaintext.

Level: Easy2 of 10
Topics: String, Simulation
Solved: No attempts yet

Problem

Alice and Bob are deeply in love. They often swap messages in class because they cannot get enough of each other. To make sure no one but them can read these messages, they devise an encryption scheme that belongs only to them. Security through obscurity does work, right?

They map each letter a-z to the numbers 0 to 25. They use a modular addition cipher with the encryption function $E$ and the decryption function $D$ :

$E(k, p) = p + k \mod 26$

$D(k, c) = c - k \mod 26$

$c_i = E(k_i, p_i)$

$p_i = D(k_i, c_i)$

Here $p$ is the plaintext, $c$ is the ciphertext, and $k$ is the key.

To avoid sending long keys, they define the key as

$k_i = p_{i-1}$

where $k_0$ is predetermined by Bob and Alice.

They believe this is secure, and they chat all day without a worry.

Eve has been spying on them. Each time they send a message, she picks up the last letter of it. She wants to find out what the messages say.

Input

One line with one integer: $1 \leq n \leq 10^3$ , the length of the ciphertext string.
One line with the ciphertext string.
One line with the last letter of the plaintext string.

Output

The plaintext string.

Examples2

Example 1
Input
```
8
ftzjzcmi
u
```
Expected output
```
iloveyou
```
Example 2
Input
```
10
ulpwzkkfco
d
```
Expected output
```
helloworld
```