Reassembling the Glass Cow

Count the triples of scattered pieces that rebuild the colored figurine after rotation, reflection, and shifting.

Medium7Brute forceGeometryMatrixHash mapNo attempts yetTime limit5sMemory limit512 MB

Problem

Farmer John decided to decorate his house a little more. At a china shop he found a delicate glass cow figurine, and since it looked right for the mantelpiece he decided to buy it.

The figurine is written as an N×MN \times M grid of characters, like the one below. A lowercase letter marks one part of the figurine, and different letters are different colors. The character . is an empty square.

...............
...............
x..x...........
xxxx...........
xxxxaaaaaaa....
.xx.aaaaaaaaa..
....aaaaaaa.aa.
....ll...ll....
....vv...vv....
...............

Just before he paid, a bull charged across the shop and smashed the figurine he wanted along with several others on the shelf. The cow figurine broke into three pieces, and they ended up mixed with the KK pieces scattered on the floor. A piece on the floor is written as a grid of characters in the same way.

A piece on the floor can lie flipped horizontally or vertically, or turned by a multiple of 90 degrees. You can move a piece, flip it, and turn it by multiples of 90 degrees. If three pieces placed this way do not overlap, cover every square of the figurine exactly once, and match every color, those three pieces rebuild the figurine.

Help Farmer John count how many combinations of three pieces out of the KK pieces on the floor rebuild the cow figurine.

Input

The first line contains one integer KK (4K1004 \le K \le 100). Then K+1K + 1 piece descriptions follow. The first description is the shape of the original cow figurine, and the next KK are the shapes of the pieces on the floor.

The first line of a piece description contains two integers RR and CC. Each of the next RR lines contains CC characters, one per square. Each character is a lowercase letter that names a color, or a . that marks an empty square. In the description of the original figurine, 3R,C5003 \le R, C \le 500; in the description of a piece on the floor, 1R,C1001 \le R, C \le 100. Every piece is connected through shared edges and has at least one square that is not empty.

Output

Print the number of combinations of pieces ii, jj, kk (i<j<ki < j < k) that rebuild the original figurine.

Note

In the example there are three combinations. They use pieces 0, 1, 2; pieces 0, 2, 4; and pieces 1, 3, 4. Pieces are numbered from 0.