##### Canadian Computing Competition: 1998 Stage 2, Day 1, Problem 2

Messages can be ciphered (encrypted) by systematically replacing letters of the alphabet with other letters. A simple cipher known as the Caesar cipher replaces each letter in the alphabet with the letter positions later in the alphabet, where `A`

is considered to follow `Z`

. For example, if , `ABCDEFGHIJKLMNOPQRSTUVWXYZ`

would be replaced by `GHIJKLMNOPQRSTUVWXYZABCDEF`

respectively. The message

`THE FULL MOON RISING IS A BAD SIGN`

would be ciphered as

`ZNK LARR SUUT XOYOTM OY G HGJ YOMT`

The inverse of the cipher is again a Caesar cipher with replacing .

Your job as a cryptanalyst is to decode lines of text that have been encoded with a Ceasar cipher, each using a different unknown value of . For example, if the input were

```
ZNK LARR SUUT XOYOTM OY G HGJ YOMT
FA NQ AD ZAF FA NQ FTMF UE FTQ CGQEFUAZ
```

the output would be

```
THE FULL MOON RISING IS A BAD SIGN
TO BE OR NOT TO BE THAT IS THE QUESTION
```

(the first line was ciphered with and the second line with ).

Of course, there are possible values of and therefore possible ciphers, so you will have to "guess" by selecting the most probable deciphering. The probability of a particular deciphering can be estimated using the probabilities of the letters it contains. In English, `E`

is the most common letter, with probability , `T`

is the next more common with probability , and so on. A complete table of letter probabilities is given below. The probability of a complete line of text can be approximated by the product of the probabilities of the letters it contains.

Letter | Probability | Letter | Probability |
---|---|---|---|

A | .082 | N | .067 |

B | .015 | O | .075 |

C | .028 | P | .019 |

D | .043 | Q | .001 |

E | .127 | R | .060 |

F | .022 | S | .063 |

G | .020 | T | .091 |

H | .061 | U | .028 |

I | .061 | V | .010 |

J | .002 | W | .023 |

K | .008 | X | .001 |

L | .040 | Y | .020 |

M | .024 | Z | .001 |

#### Input Specification

The input to your program consists of a line containing a positive integer , followed by lines, each consisting of upper case letters and spaces only. Each line is an English phrase or sentence, encrypted with a Caesar cipher with unknown .

#### Output Specification

For each line of input, give the most probable deciphering.

#### Sample Input

```
2
ZNK LARR SUUT XOYOTM OY G HGJ YOMT
FA NQ AD ZAF FA NQ FTMF UE FTQ CGQEFUAZ
```

#### Sample Output

```
THE FULL MOON RISING IS A BAD SIGN
TO BE OR NOT TO BE THAT IS THE QUESTION
```

## Comments

This might be useful

C++:

Python: