ZE(bonus) - RSA::break()

This is the inverse of problem ZD (RSA encrypt).

You will be given the output of problem ZE (hexadecimal codes of characters encrypted with RSA) as input. Your task is to print the original message. Note that since you are not given the private key, this means you will have to break the encryption. Fortunately, it is only 32 bits long.

Here is the math behind RSA encryption. To encrypt an integer, P using the public key (n, e), compute the number C as

C = P^e mod n

Since n is a product of exactly two primes, p and q, the Euler phi function of n has a simple expression

phi(n) = (p - 1)(q - 1)

Of course, when we are breaking RSA, we do not know what the two primes are, but if we somehow compute phi(n), then the next step is to find the inverse of e modulo phi(n), i.e. to find a d such that

de = 1 (mod phi(n))

This is a standard application of the extended Euclidean algorithm. d and n together are called the private key because they can be used to reverse the encryption like this.

P = C^d mod n

This works because of Euler's theorem that states

For any integer a and any positive integer n,
a^phi(n) = 1 (mod n)

In the case of RSA,

P = C^d (mod n)
P = (P^e)^d = P^de (mod n)
P = P¹P^k*phi(n) = P*1^k = P (mod n) for some integer k

Input

The input is exactly in the format of the output of problem ZD.

Output

Output the plaintext message on a single line.

Sample input

10002200057 5
5
016C182123
0217126914
011B229825
0249D48C6D

1210140803471 1100089
6
010E746CB830
001E4C23CD53
002564CA1DC8
00ED1D0A132F
00A6CCE34282
00FF954B9B7E
0021A5E3C35C
0107C8BB0462
000E5BA63D64
00978F262566
00FB81D3BC15
0021E9B6585B
00D3E5E1B9CD

Sample output

DEOXYRIBONUCLEIC
Plumes of smoke rise and merge into the leaden sky