#U1516OB2. Bull in a China Shop

Bull in a China Shop

农夫约翰决定他的家需要更多的装饰。参观当地的瓷器店时,他发现了一个精致的玻璃牛雕像,他决定购买,因为他知道它非常适合放在壁炉上方的壁炉架上。

牛雕像的形状由 N×N 字符网格描述,如下图 (3≤N≤8),其中“#”字符是雕像的一部分,而“.”字符不是雕像的一部分。

...............
...............
...............
#..#...........
####...........
############...
.##.#########..
....#######.##.
....##...##....
....##...##....
...............
...............
...............
...............
...............

不幸的是,就在 FJ 购买之前,一头公牛跑过商店,不仅打破了 FJ 的雕像,还打破了货架上的许多其他玻璃物品!FJ的人偶碎成2块,很快就消失在地上的K块(3≤K≤10)中。K 块中的每一个都由 N×N 字符网格描述,就像原始小雕像一样。

请帮助 FJ 确定 K 件中的哪两件是他需要将其粘在一起以修补破损的小雕像。幸运的是,当他的2块小雕像落到地上时,它们并没有旋转或翻转,所以要重新组装它们,FJ只需将它们水平和/或垂直移动,然后叠加起来。如果他有正确的2件,他应该能够以一种完全重建原始小雕像的方式做到这一点,原始小雕像中的每个“#”恰好代表两件之一(即,两件,移位叠加时,不应共用任何“#”字符,它们应完全形成原始形状)。

FJ 可以将1块垂直和/或水平移动任意数量的字符,但它不能移动到它的任何“#”字符超出原始 N×N 网格的程度。每件的形状不一定由“#”字符的单个“连接”区域组成;尽管如此,如果一个片段由多个不相交的“#”字符块组成,那么如果要移动整个片段,它们都必须移动相同的数量。

输入格式(文件 bcs.in):

输入的第一行包含 N,后跟 K。接下来的 N 行提供了描述 FJ 原始雕像的字符网格。接下来的 KN 行给出了 K 个字符网格,指定了 FJ 在地面上找到的 K 个块。

输出格式(文件 bcs.out):

请打印出一行,其中包含两个以空格分隔的整数,每个整数的范围为 1…K,指定两个 FJ 小雕像的索引。解决方案将永远存在,并且是独一无二的。您打印的两个数字必须按排序顺序排列。

样例输入:

4 3
####
#..#
#.##
....
.#..
.#..
##..
....
####
##..
#..#
####
....
.###
.#..
.#..

样例输出:

1 3