#3108. [Usaco2016 Open]Bull in a China Shop

[Usaco2016 Open]Bull in a China Shop

Description

农夫约翰决定他的家里需要更多的装饰。通过参观当地的瓷器商店,他决定购买一个精致的玻璃牛雕像,他知道它

将完全适合放在壁炉上方的壁炉架上。牛雕像的形状由一个N×M的字符网格(就像下图)描述(3≤N,M≤500),

其中小写字母描述了雕像的每个部分(表示不同的颜色),'.'字符则不是。

...............

...............

x..x...........

xxxx...........

xxxxaaaaaaa...

.xx.aaaaaaaaa..

....aaaaaaa.aa.

....ll...ll....

....vv...vv....

...............

不幸的是,在FJ正准备购买之前,一头公牛穿过商店,不仅打破了FJ的雕像,而且还打破了货架上的许多其他玻璃

制品! FJ的雕像碎成了3片,很快地散落在总共有K块碎片的地面上(4≤K≤100)。每块碎片由一个字符网格描述

,就像描述原来的雕像那样。请帮助FJ确定多少个3块碎片的集合(落在地板上的K块碎片中的其中3块)可以胶合

在一起修补成他的破碎的雕像。地面上的碎片可能已经水平或垂直翻转,或者旋转成了90度的几倍。因此,给定原

始网格以及描述K块碎片的网格,您需要找到3片碎片可以连接在一起以形成原始图像的集合,允许这些碎片被平移

,翻转或旋转90度的倍数。然后当叠加时,3个碎片应该准确地形成原始图形,原始图形中的每个彩色正方形正好

表示其中一片。

Format

Input

第一行包含单个整数K,接下来有K+1个描述片段,第一个片段描述了原始的玻璃牛,剩下的K个片段描述了K块碎片。

对于每个描述片段,第一行包含两个整数R和C(1≤R,C≤100),接下来R行每行C个小写字母或者是'.'。

每个碎片都将被水平/垂直连接并且具有至少一个非空单元(即至少包含一个小写字母)。

Output

输出三元组i,j,k的数目(i <j <k),使得碎片i,j,k可以被拼接为原始的玻璃牛。

Samples

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
//共有三个解决方案,分别使用碎片(1,2,3),(1,3,5),(2,4,5)。