Problem H: Caesar’s Orders

Julius Caesar uses a cipher to conceal from prying eyes the orders that he sends to his generals. This cipher, known as Caesar’s cipher, is a simple three left shift substitution cipher: each character in the original message is substituted, in the ciphered message, by the character which is three positions to the right in the alphabet. For example: A, in the original message, is substituted by a D in the ciphered message, B by E, etc, and Z by C.

Lately, Julius Caesar is growing suspicious about the secrecy of his cipher and decided to make it more secure. The new process to encipher messages uses the good old Caesar’s cipher, plus steganography (steganography is the art and science of hiding messages within messages in such a way that nobody even suspects that the hidden messages are there) and also an elaborated alphanumeric to numeric substitution.

The process of ciphering a message has four steps. It starts with C - the Caesar’s order - and M - a message in which the order will be hidden. All the messages use capital letters only. Let NC be the number of characters in C and NM be the number of characters in M.

For example, suppose C is "HOLDYOURPOSITION" and M is "ABCDEFGHIJKLMNOPQRSTUVWXYZ" (despite the example, M does not have to contain all the letters of the alphabet, but only all the letters in the message). NC is 16 and NM is 26.

  1. A Caesar’s cipher is applied to C, to obtain the ciphered order C2, with a left shift of1NC/3⌋
    Step example: With a left shift of 5 we obtain C2 = MTQIDTZWUTXNYNTS.
  2. Each character of C2 is mapped to a position of M, obtaining an integer array L.
    Step example: L = 12 19 16 8 3 19 25 22 20 19 23 13 24 13 19 18.
  3. The Caesar’s cipher is applied again, now to M, with a left shift of2NC/2⌉, producing the ciphered message M2.
  4. The final ciphered message M3 is obtained. This is the message that will be sent to the generals. In order to build M3, each character of M2 is converted to a number as follows: A is mapped to 00; B is mapped to 01; …; Z is mapped to 25.
    Step example: M3 = 0809101112131415161718192021222324250001020304050607


Your task as Roman master spy allocated to a general is to decipher the message M3 received from Julius Caesar and deliver the order C to your boss, the general.


The first line of the input contains the number NC of letters in the order issued by Julius Caesar. The second line contains a set of NC numbers separated by single space that constitute the integer array L. The last line contains the ciphered message M3.


The output consists of a single line with the order C given by Julius Caesar.


1 ≤ NC < 1,000Number of characters of the order
1 ≤ NM < 15,000Number of characters of the message

Input example 1

12 19 16 8 3 19 25 22 20 19 23 13 24 13 19 18

Output example 1


Input example 2

19 4 159 69 43 13 5 10 60 9

Output example 2


Note: the second input example has only three lines. The 3rd and last line, containing M3, is shown on paper in different lines only because of space constraints. You can however be assured that all input files will contain exactly 3 lines

x ⌋ represents the greatest integer less than or equal to x.
x ⌉ represents the smallest integer greater than or equal to x

MIUP'2012, 20 de Outubro, DCC/FCUP

This document was translated from LATEX by HEVEA.