Ethel's Encryption

Interview

Time limit1sMemory limit256 MB

Summary

Recover the plaintext by computing the Caesar shift a^b modulo 26 and moving each ciphertext letter back by that amount.

Level: Easy3 of 10
Topics: Number theory, String, Implementation
Solved: No attempts yet

Problem

Ethel suspected that the North Side Alliance (NSA) was reading the messages she exchanged with her sister Lucy. To stop them, Ethel encrypted every message with a Caesar cipher.

A Caesar cipher shifts each letter of the plaintext forward by a fixed offset to produce the ciphertext. With an offset of 2, A becomes C, B becomes D, and Y becomes A.

The offset is $a^b$ . Given the ciphertext, recover the original message.

Input

The first line contains three integers $n$ , $a$ , and $b$ . Here $n$ is the number of characters in the ciphertext, spaces included. The offset is computed as $a^b$ , with $0 \le a \le 2^{31}$ and $0 \le b \le 2^{16}$ . In every input at least one of $a$ and $b$ is greater than 0.

The second line contains the $n$ characters of the ciphertext. The ciphertext consists only of upper-case letters (A-Z) and spaces, and a newline follows it immediately.

Output

Print the decrypted message in upper-case letters on a single line. Spaces stay in the positions they occupy in the ciphertext. Print a newline immediately after that line.

Examples5

Example 1
Input
```
11 3 3
IFMMP XPSME
```
Expected output
```
HELLO WORLD
```

Example 2

Input

39 2 5
GT OTBKYZOMGZOUT UL ZNK RGCY UL ZNUAMNZ

Expected output

AN INVESTIGATION OF THE LAWS OF THOUGHT

Example 3
Input
```
5 0 1
HELLO
```
Expected output
```
HELLO
```
Example 4
Input
```
3 7 0
BCD
```
Expected output
```
ABC
```

Example 5

Input

26 5 2
ZABCDEFGHIJKLMNOPQRSTUVWXY

Expected output

ABCDEFGHIJKLMNOPQRSTUVWXYZ