P1906 Caesar Cipher

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: ```plain (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.

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`.

For each sentence, output the translated plaintext. **Please output everything in uppercase!**

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: ```plain 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