Cedric's cypher

Interview

Time limit1sMemory limit128 MB

Summary

Decrypt each Caesar-ciphered line using the trailing encrypted A to recover the shift and drop that marker.

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

Problem

A Caesar cipher encrypts text by replacing every letter with the letter $s$ places after it in the alphabet. The number $s$ is called the shift. With a shift of 5, 'A' becomes 'F', 'H' becomes 'M' and 'Y' becomes 'D', since the alphabet wraps round and 'A' follows 'Z'. Upper case letters stay upper case and lower case letters stay lower case. Anyone who knows the shift can decrypt the text easily.

Cedric changed one thing. Rather than tell his friends the shift, he encrypts the letter 'A' with that same shift, which always gives an upper case letter, and puts it at the end of his message. His friends read that letter, work out the shift and decrypt the rest.

Input

The input is a number of lines of text, terminated by a line containing only #. Each line holds 1 to 255 characters, counting the encrypted 'A' at the end.

Output

Print one line for each line of input, containing the decrypted text. Do not print the trailing encrypted 'A'. Punctuation, spaces, digits and every other non-letter character are printed unchanged.

Examples2

Example 1

Input

N hfs wjfi ymnx xjsyjshj, xt rd fqltwnymr btwpx.F
Serq Unzvygba-Wbarf vf 85 gbqnl! Unccl oveguqnl, Serq.N
Ocz lpdxf, wmjri ajs ephkzy jqzm ocz gvut yjbn.V
#

Expected output

I can read this sentence, so my algorithm works.
Fred Hamilton-Jones is 85 today! Happy birthday, Fred.
The quick, brown fox jumped over the lazy dogs.

Example 2
Input
```
Mjqqt, Btwqi!F
#
```
Expected output
```
Hello, World!
```