题目描述

题目译自 USACO 2016 US Open Contest, Platinum Problem 2. Bull in a China Shop

A bull in a China Shop 是一个英语俗语，表示与他人打交道时行为笨拙的人。

农夫 John 想买一个玻璃牛。它可用一个 $N\times M$ 的字符矩阵表示，如下图所示。小写字母是玻璃牛上不同的颜色，而 . 则表示背景。

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

不幸的是，正当他要付款时，一头牛冲进商店，撞翻了架子。架子上的许多玻璃制品——包括这个艺术品——都碎了。这个艺术品被摔成了三个碎片，且很快与地上的 $K$ 片碎片混在了一起。每个碎片按如上的方式描述。 求：在这 $K$ 片碎片中，取三个碎片能还原他意欲购买的牛 的方案有多少种。 地面上的碎片可能被垂直或水平翻转，且翻转度数是 $90°$ 的整数倍。因此，给出 $K$ 个由以上方法描述的碎片，你需要找到三片碎片，使得这三片碎片组合起来能形成原来的形状。碎片能被水平翻转，垂直翻转，旋转 $90°$ 的整数倍。当拼接完毕后，你的图像应完全符合原图。

输入格式

第一行一个数 $K$，接下来将有 $K+1$ 片碎片，第一片描述原图，接下来 $K$ 片是碎片。
每个描述的第一行有两个数 $R$ 与 $C$，接下来由 $R$ 行 $C$ 列小写字母描述每个网格，整个碎片互相连通，且至少有一个非空格。

输出格式

输出三元组 $(i, j, k)\ (i<j<k)$ 使得 $i, j, k$ 三片能形成原图的数量。

5
5 5
aaaaa
..a..
bbabb
..a..
aaaaa
3 5
..abb
..a..
aaaaa
5 2
a.
a.
aa
a.
a.
1 2
bb
1 5
bbabb
2 5
aaaaa
..a..

3

数据范围与提示

$4 \le K \le 100, 3 \le N,M \le 500, 1 \le R,C \le 100$。