Hide

Problem E
Over the Hill, Part 1

Hill encryption (devised by mathematician Lester S. Hill in 1929) is a technique that makes use of matrices and modular arithmetic. It is ideally used with an alphabet that has a prime number of characters, so we’ll use the 37 character alphabet A, B, , Z, 0, 1, , 9, and the space character. The steps involved are the following:

  1. Replace each character in the initial text (the plaintext) with the substitution A0, B1, , (space)36. If the plaintext is ATTACK AT DAWN this becomes

    0 19 19 0 2 10 36 0 19 36 3 0 22 13
  2. Group these number into three-component vectors, padding with spaces at the end if necessary. After this step we have

    (01919)(0210)(36019)(3630)(221336)
  3. Multiply each of these vectors by a predetermined 3×3 encryption matrix using modulo 37 arithmetic. If the encryption matrix is

    (301942375913)

    then the first vector is transformed as follows:

    (301942375913)(01919)=((30×0+1×19+9×19)mod37(4×0+23×19+7×19)mod37(5×0+9×19+13×19)mod37)=(51511)
  4. After multiplying all the vectors by the encryption matrix, convert the resulting values back to the 37-character alphabet and concatenate the results to obtain the encrypted ciphertext. In our example the ciphertext is FPLSFA4SUK2W9K3.

This method can be generalized to work with any n×n encryption matrix in which case the initial plaintext is broken up into vectors of length n. For this problem you will be given an encryption matrix and a plaintext and must compute the corresponding ciphertext.

Input

Input begins with a line containing a positive integer n10 indicating the size of the matrix and the vectors to use in the encryption. After this are n lines each containing n integers (each between 0 and 36) specifying the encryption matrix. After this is a single line containing the plaintext consisting of 1 to 100 characters in the 37-character alphabet specified above.

Output

Output the corresponding ciphertext on a single line.

Sample Input 1 Sample Output 1
3
30 1 9
4 23 7
5 9 13
ATTACK AT DAWN
FPLSFA4SUK2W9K3

Sample Input 2 Sample Output 2
6
26 11 23 14 13 16
6 7 32 4 29 29
26 19 30 10 30 11
6 28 23 5 24 23
6 24 1 27 24 20
13 9 32 18 20 18
MY HOVERCRAFT IS FULL OF EELS
W4QVBO0NJG5 Y76H5A6XHR11BV670Z
Hide

Please log in to submit a solution to this problem

Log in