#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

The RSA cryptosystem is a famous cryptosystem that is widely used in many applications. Little Joseph wanted to make his own RSA cryptosystem but has made a simple one that is easy to decrypt. Your task is to decrypt Little Joseph’s code.

This is how Little Joseph encrypted his code:

### Preparation

- He only has upper-case characters so he converted all the characters into numbers (A = 1, B = 2… etc), let’s call his character
*P*. - He secretly selected two prime numbers
*p*and*q*. - He multiplied both prime numbers
*p*and*q*to get*n*, as well as evaluated*m*= (*p*- 1)(*q*- 1) - Then, he picked an integer
*e*in the range of*1*to*n*such there is an integer*d*such that (*e***d*) %*m*= 1. (The remainder when*e***d*divided by*m*is 1.)

### Encryption

To encrypt it, the crypted code *C* is actually *P ^{e}* %

*n*

### Decryption

To decrypt it, one can use the following computation: *P* is actually *C ^{d}* %

*n*. Convert this back into upper case using

*P*= ('A' +

_{char}*P*- 1) % 256 where

*P*is the ASCII code for the original character.

_{char}## Task

The first line consists of an integer *T*, being either 1 or 2.

If *T* is 1:

The second line consists of the numbers *n*, *e* and *c* (the number of letters in the original code).

The encrypted code is on the third line.

If *T* is 2:

The second line consists of the numbers *n*, *d* and *c* (the number of letters in the original code).

The encrypted code is on the third line.

For both tasks, print out the original (decrypted) code (in upper-case letters). Note, there is a space between each upper-case letters if there are 2 or more letters.

## Limits

For 20% of the test cases, *T* will be 2 (*d* will be given to you instead of *e*).

For 50% of the test cases, *n* < 1000.

For 100% of the test cases, *n* < 100000, *c* < 10.

## Sample Input 1

1 77 43 1 30

## Sample Output 1

B

## Explanation

*p* is 7 and *q* is 11, hence *n* is 77 and *m* is 60. *e* is 43 and *d* is 7 (43 * 7 % 60 == 1). (30^{7} % 77 is 2, and this corresponds to B).

## Sample Input 2

2 77 7 1 30

## Sample Output 2

B

## Explanation

This is the same as the above case, just that *d* is already given as 7. Using the same decryption, this will correspond to B.

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 100 | 6 | 1s | 32MB | Average |

2 | 0 | 2 | 1s | 32MB | Average |

### Judge Compile Command

g++-8 ans.cpp -o rsaeasy -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512