Dominoes

For a given N, there is one domino labeled (i, j) for every pair 1 <= i, j <= N, so there are N^2 dominoes in total.

The dominoes are placed on an N x N board. The cell in row i and column j contains the domino labeled (i, j).

A player must choose exactly N dominoes. No two chosen dominoes may have the same first number, and no two chosen dominoes may have the same second number. Equivalently, exactly one domino is chosen from each row and each column.

The chosen dominoes split into one or more cycle groups. A domino (a, b) can be followed by a domino whose first number is b; if the second number of the last domino equals the first number of the first domino, those dominoes form a cycle. A single domino (x, x) forms a cycle group by itself. Every valid selection can always be decomposed into such cycles.

Each domino also has a value written on its back. The score is the product of the back values of all chosen dominoes. After that, if the number of cycle groups is even, multiply the score by -1.

Given the back values of all dominoes, find the minimum and maximum scores that can be obtained.

The first line contains a positive integer N. N is at most 6.

The next N lines each contain a string of length N. The jth character of the ith line is the back value of domino (i, j).

Each character is either a digit from 0 to 9 or an uppercase letter from A to I. Digits mean the values 0 through 9, and letters A through I mean the values -1 through -9, respectively.

Print the minimum obtainable score on the first line.

Print the maximum obtainable score on the second line.