Rope

Task

You are given a board of $n \cdot n$ square cells. Each cell contains a tile of one of the following three types:

For example, we could have the following configuration:

A rope is a maximal connected sequence of segments occurring in the tiling; e.g., a rope is highlighted above in red. (We assume the two segments in type $3$ tiles do not touch.) A rope's length is defined as the number of segments it contains; thus, the rope highlighted in red has a length of $16$. Note that segments from a type $3$ cell count the same as segments from type $1$ or type $2$ cells, even though they are geometrically longer.

You are asked the following:

• Compute the number of V-shaped length-$2$ ropes with extremities on the edge of the board. Moreover, compute the number of rhombuses, which are defined as length-$4$ ropes that do not have extremities on the edge of the board. In other words, find the number of shapes that look like this:

• Compute the length of the longest rope that starts on the edge of the board. For instance, this rope is highlighted in red in the diagram above.
• Change the type of exactly one tile such that the length of the longest rope with extremities on the edge of the board is maximized; also compute the number of ways this can be done to maximize this length. It is guaranteed that a way to change a tile that leads to a longer maximum rope length always exists. For example, replacing one of the highlighted tiles below is optimal for the configuration in the diagram above. The corresponding new longest ropes are again drawn in red.

Input data

On the first line, there are two integers $p$ and $n$, representing which of the three problems you should solve ($1, 2$ or $3$) and the number of rows and columns of the board. The following $n$ lines describe the contents of the board, each line describing a row of the board. Tiles on a row are not space-separated.

Output data

Depending on the value of $p$, output the following:

1. If $p = 1$, output two integers: the number of V-shaped ropes with extremities on the sides of the board and the number of rhombuses, respectively;
2. If $p = 2$, output the length of the longest rope with extremities on the edge of the board;
3. If $p = 3$, output two integers: the length of the longest rope with extremities on the edge of the board that can be obtained if the type of exactly one tile is changed and the number of ways of achieving this maximum. Note: if a tile can be changed in two ways to achieve the maximum, it counts as two different ways.

Constraints and clarifications

• $1 \leq n \leq 2\ 000$
• For $20$ points: $p = 1$.
• For another $40$ points: $p = 2$.
• For another $40$ points: $p = 3$.
• There are $10$ testcases where $p = 2$ and $10$ testcases where $p = 3$. The values of $n$ on these testcases are: $5, 50, 75, 908, 991, 1401, 1593, 1842, 1971, 2000$.
• The tests for this task are scored individually!

Example 1

stdin

1 5
23211
11232
22123
13232
22312

stdout

5 1

Example 2

stdin

2 5
23211
11232
22123
13232
22312

stdout

16

Example 3

stdin

3 5
23211
11232
22123
13232
22312

stdout

22 2

Example 4

stdin

3 5
23211
11232
22123
13232
22312

stdout

14 4

Explanations

In the first three examples, the board's configuration is as in the first diagram.

For the first example, we count the number of v-shaped ropes of length $2$ with extremities on the edge of the board and the number of rhombuses, and output that there are five v-shaped ropes and one rhombus.

For the second example, the longest rope has a length of $16$, as highlighted in the diagram above.

For the third example, we can get a rope length of $22$ by changing the highlighted tile. We could also have changed the tile on row $1$ and column $2$ from type $3$ to type $1$; thus we output that there are two ways of changing a tile so that the maximum length of a rope is $22$.

The fourth example is another board. There are four ways to get to ropes of length $14$.