题目描述

In this problem, a grid is an $N$-by-$N$ array of cells, where each cell is either red or white.

Some grids are similar to other grids. Grid $A$ is similar to grid $B$ if and only if $A$ can be transformed into $B$ by some sequence of changes. A change consists of selecting a $2$-by-$2$ square in the grid and flipping the colour of every cell in the square. (Red cells in the square will become white; white cells in the square will become red.)

You are given $G$ grids. Count the number of pairs of grids which are similar. (Formally, number the grids from $1$ to $G$, then count the number of tuples $(i, j)$ such that $1 \le i < j \le G$ and grid $i$ is similar to grid $j$.)

输入格式

The first line of input contains $N\ (2 \le N \le 10)$, the size of the grids. The second line contains $G\ (2 \le G \le 10\,000)$, the number of grids. The input then consists of $N \cdot G$ lines, where each line contains $N$ characters, where each character is either R or W, indicating the colour (red or white) for that element in the grid. Moreover, after the first two lines of input, the next $N$ lines describe the first grid, the following $N$ lines describe the second grid, and so on.

For $12$ out of the $25$ marks available for this question, $2 \le G \le 10$.

输出格式

Output the number of pairs of grids which are similar.

2
2
RW
WR
WR
RW

1

提示

There are exactly two grids, and they are similar because the first grid can be transformed into the second grid using one change (selecting the $2$-by-$2$ square consisting of the entire grid).