Reconstructing the Figurine

Farmer John's delicate glass cow figurine has been broken into 3 pieces, and it is lost among K total broken pieces lying on the ground. The original figurine is represented by an \(N \times M\) grid, where each lowercase letter represents a colored cell of the figurine and the '.' (dot) represents an empty cell. Similarly, each of the K pieces is given as a grid with letters and dots. A valid reassembly requires that three chosen pieces, after applying any combination of translations, rotations (by \(0^\circ\), \(90^\circ\), \(180^\circ\), or \(270^\circ\)), and flips (horizontal or vertical) to each piece, can be superimposed without overlap to exactly match the original figurine. In other words, when the 3 pieces are placed on top of one another in some configuration, every colored cell in the original must be covered exactly once by a cell in one of the pieces, and the letters must match.

Determine how many sets of 3 pieces (from the K pieces on the floor) can be assembled to form the original figurine.

Note: The transformed pieces must lie entirely within the boundaries of the original grid, and a cell from a piece can only be used if its letter matches the corresponding cell in the original figurine.

inputFormat

The input begins with two integers \(N\) and \(M\) (\(3 \le N, M \le 500\)) representing the dimensions of the original figurine. Following this are \(N\) lines, each with \(M\) characters (each either a lowercase letter or a dot), describing the original figurine.

The next line contains an integer \(K\) (\(4 \le K \le 100\)), the total number of broken pieces on the ground. Then for each piece, the description is as follows:

• A line containing two integers \(r\) and \(c\) indicating the number of rows and columns of this piece.
• Followed by \(r\) lines, each with \(c\) characters (each either a lowercase letter or a dot) describing the piece.

It is guaranteed that the pieces are such that colors (letters) are significant; that is, when superimposing a piece, its letter at each cell must match the corresponding letter of the original figurine.

outputFormat

Output a single integer: the number of sets of 3 pieces (chosen from the K pieces) that can be reassembled (using any combination of translation, rotation, and flipping) to form the original figurine exactly.

sample

3 3
abc
def
ghi
3
1 3
abc
1 3
def
1 3
ghi

1