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 Pe % n
Decryption
To decrypt it, one can use the following computation: P is actually Cd % n. Convert this back into upper case using Pchar = ('A' + P - 1) % 256 where Pchar is the ASCII code for the original character.
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). (307 % 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.