RSA is one of the most powerful methods to encrypt data. The RSA algorithm is described as follow:
> choose two large prime integer p, q > calculate n = p × q, calculate F(n) = (p - 1) × (q - 1) > choose an integer e(1 < e < F(n)), making gcd(e, F(n)) = 1, e will be the public key > calculate d, making d × e mod F(n) = 1 mod F(n), and d will be the private key
You can encrypt data with this method :
C = E(m) = me mod n
When you want to decrypt data, use this method :
M = D(c) = cd mod n
Here, c is an integer ASCII value of a letter of cryptograph and m is an integer ASCII value of a letter of plain text.
Now given p, q, e and some cryptograph, your task is to "translate" the cryptograph into plain text.
Each case will begin with four integers p, q, e, l followed by a line of cryptograph. The integers p, q, e, l will be in the range of 32-bit integer. The cryptograph consists of l integers separated by blanks.
For each case, output the plain text in a single line. You may assume that the correct result of plain text are visual ASCII letters, you should output them as visualable letters with no blank between them.