Canadian Computing Olympiad: 2016 Day 2, Problem 1

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$.)

Input Specification

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 10000)$, 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 Specification

Output the number of pairs of grids which are similar.

Sample Input

2
2
RW
WR
WR
RW

Sample Output

1

Explanation

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).