Over the hill 1

题号：NC226973
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

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:

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$
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)$
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{aligned} \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(0) + 1(19) + 9(19)) \mod 37 \\ %(4(0) + 23(19) + 7(19)) \mod 37 \\ %(5(0) + 9(19) + 13(19)) \mod 37 (30 \times 0 + 1 \times 19 + 9 \times 19) \mod 37 \\ (4 \times 0 + 23 \times 19 + 7 \times 19) \mod 37 \\ (5 \times 0 + 9 \times 19 + 13 \times 19) \mod 37 \end{array} \right) \\ & = & \left( \begin{array}{c} 5 \\ 15 \\ 11 \end{array} \right)\end{aligned}$
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 begins with a line containing a positive integer  indicating the size of the matrix and the vectors to use in the encryption. After this are  lines each containing  non-negative integers specifying the encryption matrix. After this is a single line containing the plaintext consisting only of characters in the -character alphabet specified above.

输出描述:

Output the corresponding ciphertext on a single line.

示例1

输入

复制

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

输出

复制

FPLSFA4SUK2W9K3

示例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

备注:

The length of the strings <=100