#aising2019c. [aising2019_c]Alternating Path

[aising2019_c]Alternating Path

Problem Statement

There is a grid with HH rows and WW columns, where each square is painted black or white.

You are given HH strings S1,S2,...,SHS_1, S_2, ..., S_H, each of length WW. If the square at the ii-th row from the top and the jj-th column from the left is painted black, the jj-th character in the string SiS_i is #; if that square is painted white, the jj-th character in the string SiS_i is ..

Find the number of pairs of a black square c1c_1 and a white square c2c_2 that satisfy the following condition:

  • There is a path from the square c1c_1 to the square c2c_2 where we repeatedly move to a vertically or horizontally adjacent square through an alternating sequence of black and white squares: black, white, black, white...

Constraints

  • 1leqH,Wleq4001 \\leq H, W \\leq 400
  • Si=W|S_i| = W (1leqileqH1 \\leq i \\leq H)
  • For each ii (1leqileqH1 \\leq i \\leq H), the string SiS_i consists of characters # and ..

Input

Input is given from Standard Input in the following format:

HH WW S1S_1 S2S_2 :: SHS_H

Output

Print the answer.


Sample Input 1

3 3
.#.
..#
#..

Sample Output 1

10

Some of the pairs satisfying the condition are ((1,2),(3,3))((1, 2), (3, 3)) and ((3,1),(3,2))((3, 1), (3, 2)), where (i,j)(i, j) denotes the square at the ii-th row from the top and the jj-th column from the left.


Sample Input 2

2 4
....
....

Sample Output 2

0

Sample Input 3

4 3
###
###
...
###

Sample Output 3

6