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 of1 ⌊NC/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 of2 ⌈NC/2⌉, producing the ciphered message M2.
    Step example: M2 = IJKLMNOPQRSTUVWXYZABCDEFGH.
  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

Task

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.

Input

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.

Output

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

Constraints

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

Input example 1

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

Output example 1

HOLDYOURPOSITION

Input example 2

10
19 4 159 69 43 13 5 10 60 9
241209101619192205180807091316131811102518072413191805220925232505161603240320092309
240113241216091024051808221311122423212505220906220507150924230112092209241209252020
092210192210161919221025180724131918192216190109221019220709131613181110251807241319
181219221304191824051606052223052209171323231318110603220517051825140518

Output example 2

RIGHTFLANK


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

1
⌊ x ⌋ represents the greatest integer less than or equal to x.
2
⌈ 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.