Description

With the support of the Senate, Caesar led the Roman legions to attack the region of Gaul. However, his campaign did not go smoothly, and he urgently needs your help.

One day, you suddenly receive a letter from Caesar written from the front. To prevent the enemy from stealing intelligence, Caesar decided to write the letter using a cipher of his own design. But faced with a page of gibberish, you are at a loss, so you go to the Senate to ask about the secret behind this cipher.

The elders tell you that this is the Caesar shift cipher (the world's earliest encryption technique — Editor's note), and decoding it is very simple:

For each letter in the plaintext, Caesar replaces it with the $t$-th letter after it. For example, when $t = 2$, the letter A becomes C, B becomes D, ... , Y becomes A, and Z becomes B (assuming the alphabet is cyclic).

Thus:

(t = 2)

[Plain Text]   A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
[Cipher]       C D E F G H I J K L M N O P Q R S T U V W X Y Z A B

[Plain Text]   I Need Soldiers
[Cipher]       K Pggf Uqnfkgtu

In this way, the message appears like an indecipherable text to outsiders. Moreover, Caesar will occasionally change the value of $t$, making the cipher even harder to grasp.

Your task is to translate Caesar's ciphertext into plaintext.

Input Format

You will be given several pieces of Caesar's ciphertext, and we guarantee that each is a coherent English sentence. The input file is guaranteed to be smaller than 50 KB.

Each sentence starts with a line START, the next line contains the sentence, and the following line is END. The entire input ends with ENDOFINPUT.

Output Format

For each sentence, output the translated plaintext.

Please output everything in uppercase!

START
NS BFW, JAJSYX TK NRUTWYFSHJ FWJ YMJ WJXZQY TK YWNANFQ HFZXJX
END
START
N BTZQI WFYMJW GJ KNWXY NS F QNYYQJ NGJWNFS ANQQFLJ YMFS XJHTSI NS WTRJ
END
START
IFSLJW PSTBX KZQQ BJQQ YMFY HFJXFW NX RTWJ IFSLJWTZX YMFS MJ
END
ENDOFINPUT

IN WAR, EVENTS OF IMPORTANCE ARE THE RESULT OF TRIVIAL CAUSES
I WOULD RATHER BE FIRST IN A LITTLE IBERIAN VILLAGE THAN SECOND IN ROME
DANGER KNOWS FULL WELL THAT CAESAR IS MORE DANGEROUS THAN HE

Hint

1. If you have read The Adventures of Sherlock Holmes, recall the first step in cracking the cipher in "The Dancing Men".
2. These may help you:

e 0.1268
t 0.0978
a 0.0788
o 0.0766
i 0.0707
n 0.0706
s 0.0634
r 0.0594

Based on extensive statistics, in well-formed English sentences the letter E appears most frequently.

You need to determine the value of $t$ using this property.

The testdata guarantees that this property uniquely determines the value of $t$.

Translated by ChatGPT 5