E. Over the Hill, Part 1
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

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, $$$\ldots$$$, Z, 0, 1, $$$\ldots$$$, 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$$$\rightarrow 0$$$, B$$$\rightarrow 1$$$, $$$\ldots$$$, (space)$$$ \rightarrow 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
  3. Multiply each of these vectors by a predetermined $$$3 \times 3$$$ encryption matrix using modulo $$$37$$$ arithmetic. If the encryption matrix is

    then the first vector is transformed as follows:

  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 \leq 10$$$ indicating the size of the matrix and the vectors to use in the encryption. After this are $$$n$$$ lines each containing $$$n$$$ non-negative integers specifying the encryption matrix. After this is a single line containing the plaintext consisting only of characters in the $$$37$$$-character alphabet specified above.

Output

Output the corresponding ciphertext on a single line.

Examples
Input
3
30 1 9
4 23 7
5 9 13
ATTACK AT DAWN
Output
FPLSFA4SUK2W9K3
Input
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
Output
W4QVBO0NJG5 Y76H5A6XHR11BV670Z