Matches

Time limit1.5sMemory limit256 MB

Summary

Given a spanning tree drawn on a grid of tokens with matches, count the ways to remove one match and add another so the graph stays a valid crossing-free spanning tree.

Level: Hard8 of 10
Topics: Graph, Union-find, Implementation
Solved: No attempts yet

Problem

Mirko found a pile of tokens and matches. He arranged the tokens in a regular rectangular grid of $R$ rows and $S$ columns. Two tokens are adjacent if they are in the same or adjacent rows and in the same or adjacent columns. So each token has at most 8 adjacent tokens. He then placed matches between some pairs of adjacent tokens. Two tokens are connected if there is a path from the first token to the second over one or more matches. Mirko placed the matches so that every pair of tokens is connected and no two matches cross each other. The figure below shows nine tokens and the matches that connect them.

To record the match positions uniquely, each token gets a 4-bit number defined as follows:

The bit of weight 1 marks a match to the upper-right adjacent token.
The bit of weight 2 marks a match to the right adjacent token.
The bit of weight 4 marks a match to the lower-right adjacent token.
The bit of weight 8 marks a match to the lower adjacent token.

Converting each 4-bit number to one hexadecimal digit, the match positions are written as an $R \times S$ matrix of hexadecimal digits.

Write a program that counts the ways Mirko can move one match to some other position so that every pair of tokens is still connected and no two matches cross each other.

A way is a pair of one match to move and one new position. The new position must be a pair of adjacent tokens that has no match yet. Two matches cross only when they lie on the two diagonals of the same unit square.

Input

The first line contains two integers $R$ and $S$ ( $2 \le R, S \le 100$ ), the number of rows and columns of the token grid.

Each of the next $R$ lines contains $S$ hexadecimal digits. The characters 0 to 9 stand for the numbers 0 to 9, and the characters A to F stand for the numbers 10 to 15.

Output

Print on a single line the number of ways to move one match so that all tokens stay connected and no two matches cross.

Examples3

Example 1
Input
```
2 2
20
30
```
Expected output
```
5
```
Example 2
Input
```
3 2
88
88
20
```
Expected output
```
20
```
Example 3
Input
```
3 3
8E8
FA8
220
```
Expected output
```
43
```