언덕 너머, 파트 1

힐 암호(Hill encryption)는 수학자 Lester S. Hill이 1929년에 고안한 기법으로, 행렬과 모듈로 연산을 활용한다. 문자 수가 소수인 알파벳과 함께 쓰면 이상적이므로, 여기서는 $37$글자 알파벳 A, B, $\ldots$, Z, 0, 1, $\ldots$, 9와 공백 문자를 사용한다. 과정은 다음과 같다:

1. 초기 텍스트(평문)의 각 문자를 A$\rightarrow 0$, B$\rightarrow 1$, $\ldots$, (공백)$\rightarrow 36$으로 치환한다. 평문이 ATTACK AT DAWN이라면 $0\ 19\ 19\ 0\ 2\ 10\ 36\ 0\ 19\ 36\ 3\ 0\ 22\ 13$이 된다.
2. 이 수들을 세 성분 벡터로 묶고, 필요하면 끝에 공백을 덧대어 채운다. 이 단계를 거치면 \[ \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. 각 벡터에 미리 정해진 $3 \times 3$ 암호화 행렬을 모듈로 $37$ 연산으로 곱한다. 암호화 행렬이 \[ \left( \begin{array}{ccc} 30 & 1 & 9 \ 4 & 23 & 7 \ 5 & 9 & 13 \end{array} \right) \]라면 첫 번째 벡터는 다음과 같이 변환된다: \[\begin{eqnarray*} \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) \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{eqnarray*}\]
4. 모든 벡터에 암호화 행렬을 곱한 뒤, 결과 값을 $37$글자 알파벳으로 되돌리고 이어 붙여 암호화된 암호문을 얻는다. 위 예에서 암호문은 FPLSFA4SUK2W9K3이다.

이 방법은 임의의 $n \times n$ 암호화 행렬로 일반화할 수 있으며, 이때 초기 평문은 길이 $n$의 벡터로 나뉜다. 이 문제에서는 암호화 행렬과 평문이 주어지면 대응하는 암호문을 계산해야 한다.

입력은 암호화에 사용할 행렬과 벡터의 크기를 나타내는 양의 정수 $n \leq 10$이 있는 줄로 시작한다. 그다음 $n$개 줄에 각각 암호화 행렬을 나타내는 $n$개의 음이 아닌 정수가 주어진다. 그다음 줄에는 위에서 지정한 $37$글자 알파벳의 문자로만 이루어진 평문 한 줄이 주어진다.

대응하는 암호문을 한 줄에 출력한다.