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, $\dots$, Z, 0, 1, $\dots$, 9, and the space character. The steps involved are the following:

1. Replace each character in the initial text (the plaintext) with the substitution A$\to 0$, B$\to 1$, $\dots$, (space)$\to 36$. If the plaintext is ATTACK AT DAWN this becomes

   $0191902103601936302213$

2. Group these number into three-component vectors, padding with spaces at the end if necessary. After this step we have

   $$\left(\begin{array}{c}0\\ 19\\ 19\end{array}\right)\left(\begin{array}{c}0\\ 2\\ 10\end{array}\right)\left(\begin{array}{c}36\\ 0\\ 19\end{array}\right)\left(\begin{array}{c}36\\ 3\\ 0\end{array}\right)\left(\begin{array}{c}22\\ 13\\ 36\end{array}\right)$$

3. Multiply each of these vectors by a predetermined $3\times 3$ encryption matrix using modulo $37$ arithmetic. If the encryption matrix is

   $$\left(\begin{array}{ccc}30& 1& 9\\ 4& 23& 7\\ 5& 9& 13\end{array}\right)$$

   then the first vector is transformed as follows:

   $$\begin{array}{rcl}\left(\begin{array}{ccc}30& 1& 9\\ 4& 23& 7\\ 5& 9& 13\end{array}\right)\left(\begin{array}{c}0\\ 19\\ 19\end{array}\right)& =& \left(\begin{array}{c}(30\times 0+1\times 19+9\times 19)\mathrm{mod}37\\ (4\times 0+23\times 19+7\times 19)\mathrm{mod}37\\ (5\times 0+9\times 19+13\times 19)\mathrm{mod}37\end{array}\right)\\ & =& \left(\begin{array}{c}5\\ 15\\ 11\end{array}\right)\end{array}$$

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\times 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 $n\le 10$ 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.

3
30 1 9
4 23 7
5 9 13
ATTACK AT DAWN

FPLSFA4SUK2W9K3

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