Over the Hill, Part 2

Time limit1sMemory limit1024 MB

Summary

Given n and one plaintext and ciphertext pair, find the n by n Hill cipher matrix modulo 36, or report no solution or too many solutions.

Level: Medium7 of 10
Topics: Matrix, Math, Number theory
Solved: No attempts yet

Problem

Bob Roberts is part of a covert espionage team at the CIA (Chocolate Institute of Alabama). He is trying to decrypt the messages of their rivals at the NSA (Nougat Society of Arkansas). The NSA uses the Hill encryption scheme from the previous problem, which is vulnerable to a known-plaintext attack. Bob has intercepted one plaintext and ciphertext pair, and he knows the size of the encryption matrix the NSA uses. He believes the encryption matrix can be determined from this information, but nobody on his staff knows how. Bob asks you to solve this for them. The intercepted data may not be enough to determine the matrix uniquely, or the data may be corrupted so that no valid matrix exists.

Input

The first line contains a positive integer $n \leq 10$ , the size of the encryption matrix and the vectors. The second line contains the plaintext and the third line contains the ciphertext. Both lines consist only of the characters $A$ , $\ldots$ , $Z$ , $0$ , $\ldots$ , $9$ and the space character. The two strings have the same length, and that length is a multiple of $n$ . Either string may have trailing spaces.

Output

If no encryption matrix is consistent with the input, print No solution. If the input is consistent but does not uniquely determine the matrix, print Too many solutions. Otherwise, print the encryption matrix with one row per line and a single space between values in a row.

Examples3

Example 1

Input

3
ATTACK AT DAWN 
FPLSFA4SUK2W9K3

Expected output

30 1 9
4 23 7
5 9 13

Example 2
Input
```
3
ATTACK
FPLSFA
```
Expected output
```
Too many solutions
```

Example 3

Input

3
ATTACK AT DAWN 
EPLSFA4SUK2W9K3

Expected output

No solution