RoAlgo Contest #9 | Lark and Nightingale

Task

There are two birds, a Lark and a Nightingale. They live in a $N×N$ grid of characters, either A, B, or .. A is a position that can be claimed by the Lark, and B is a position that can be claimed by the Nightingale, and . is a position neither of them can claim.

The Lark (A) wants to claim a piece of land in the form of a single square. She wants to maximize the area of this square, and the total number of positions in the square is her final score. Below on the right is the maximum size square (with a score of $9$) she can claim (represented by X).

.BB..A .BB..A
.B...A .B...A
BBBAAA BBBXXX
BBBAAA BBBXXX
..BAAA ..BXXX
...... ...... 

The Nightingale (B) wants to claim a piece of land in the form of a single square, rotated $45$ degrees. (You could also think of this shape as a diamond). He wants to maximize the area of this square, and the total number of positions in the square is his final score. Below on the right is the maximum size square (with a score of $5$) he can claim (represented by X).

.BB..A .BB..A
.B...A .X...A
BBBAAA XXXAAA
BBBAAA BXBAAA
..BAAA ..BAAA
...... ......  

The following are some examples of squares (for the Lark) and rotated squares/diamonds (for the Nightingale):

..... ..... XXXXX
..... ..XX. XXXXX
..X.. ..XX. XXXXX
..... ..... XXXXX
..... ..... XXXXX

..... ..... ..X..
..... ..X.. .XXX.
..X.. .XXX. XXXXX
..... ..X.. .XXX.
..... ..... ..X..

Help both of them achieve their goals fast!

Input data

First there is a single integer $N$, representing the size of the grid.

Next come $N$ lines of $N$ characters, either A, B, or ., representing positions that can be claimed by the Lark, positions that can be claimed by the Nightingale, and positions that can be claimed by neither, respectively.

Output data

Output two values, the final score (greatest area) of the Lark and the final score (greatest area) of the Nightingale, respectively.

Constraints and clarifications

• $N \leq 1 \ 000$;

Example

stdin

6
.BB..A
.B...A
BBBAAA
BBBAAA
..BAAA
......

stdout

9 5

Explanation

The explanation for the sample test case is written in the statement.