Mars Mining Transportation

In the year $2xyz$, humanity has migrated to Mars. To support the booming industrial needs, mining activities have been initiated on Mars. The mining area is a regular hexagon with side length $N$, and it is subdivided into $6 \times N \times N$ equilateral triangles (see Figure 1). Within the area there are three mines labeled A, B, C, and three refineries labeled a, b, c. Each triangular cell may represent a mine, a refinery, a mountain, or plain land.

The administration plans to construct a transportation network with three roads, each connecting a mine with its corresponding refinery. A road may only be built along an edge between two adjacent triangular regions (two triangles sharing a common edge) at a cost of $1$ per segment, and roads cannot be built on mountains. Furthermore, the three roads must be pairwise non-intersecting (i.e. no triangular cell is used by two different roads).

Your task is to determine the minimum total cost required to build such a network, and also count the number of distinct schemes achieving that cost.

inputFormat

The first line contains an integer $N$, the side length of the hexagon. This is followed by $6 \times N \times N$ lines, each containing a single character that describes the cell type. The allowed characters are:

• A, B, C: Mines
• a, b, c: Refineries
• M: Mountain (roads cannot be built here)
• .: Plain land

outputFormat

Output two integers separated by a space: the minimum total cost and the number of schemes achieving that cost.

sample

1
A
B
C
a
b
c

0 1