Description

小Y高中毕业了，等待着他的是四年未知的大学生活，小Y不禁感到既紧张又兴奋。他现在真恨不得马上就开始他的大学生 活，但是，在上学之前还是有很多事情要做的，其中很重要的一件事就是收拾行李。

小Y有一套钟爱的玩具，这套玩具由很多小的基块组成，每个基块都是由若干厚度一定的单位小正方形块拼成的连通图形，图1就是3个基块的平面图。 由于小Y非常喜欢这套玩具，他决定把它带到大学去。“我可以制作一个矩形的有一定厚度的箱子，然后把我的所有玩具都摆放到这个箱子里。”小Y自言自语道。由于箱子的厚度有限，在摆放的时候基块之间不能重叠。但是可以将基块旋转0度，90度，180度或者270度后再进行摆放，图2就是一种可能的摆放方式。 由于要带走的行李实在是太多了，小Y必须尽量缩小这套玩具所占的体积。“由于箱子的厚度是一定的，我只要适当的摆放这些基块，使得包含它们的矩形面积最小就可以了。”小Y想。但这并不是一个容易的问题，小Y试了很长时间都没有成功，你能帮帮他吗？

Format

Input

输入文件graduate1.in到graduate10.in已经放在用户目录中。

每个输入文件的第一行都是一个整数 n ，表示基块的数目。接下来是每个基块的形状描述，共有n个部分，每个部分的第一行是一个整数 r ，表示包含这个基块的最小矩形纵向上的单位小正方形的个数，接下来r行每行用一个字符串来描述基块的形状，组成该基块的单位小正方形用字符“*”来表示。数据保证每个基块的所有的单位小正方形是四连通的。

Output

本题是一道提交答案式的题目，你需要提供十个输出文件从graduate1.out到graduate10.out，放在用户目录中。

每个文件的第一行包含两个整数H和 W ，分别表示包含这些基块的最小矩形的纵向和横向尺寸。

接下来的n行，每行包含三个整数 k ，x和 y 。k是0，1，2，3四个数中的一个，表示每个基块的旋转角度，0表示不旋转，1表示顺时针旋转90度，2表示顺时针旋转180度，3表示顺时针旋转270度。x和y表示旋转后，包含该基块的最小矩形的左上角方格的坐标，x表示该方格所在的行，y表示该方格所在的列，注意行和列的编号从0开始。

Samples

3
3
*****
*   *
*****
2
*
*
5
****
*
*
*
*

4 6
0 0 1
1 1 2
3 0 0

Limitation

【样例说明】

基块的摆放方法如图3所示

【评分方法】

Ø 如果你输出的矩形的长或者宽超过500，该测试点0分。 Ø 如果你输出的方案不合法，即 k , x , y的范围不符合题目规定、某个基块超出边界或者基块之间有重叠等，该测试点0分。 Ø 否则该测试点的得分按如下公式计算 其中，your_area为你输出的矩形的面积，best_area为我们的最优结果。

【你如何测试你的输出】

我们提供graduate_check这个工具作为测试你的输出文件的办法。使用这个工具的方法是： graduate_check <测试点编号X> 在你调用这个文件后，graduate_check将根据输入文件graduateX.in和你给出的输出文件graduateX.out给出测试的结果。 检查程序的第一步是读取选手输出并尝试进行放置。程序按照输入文件的顺序依次处理各个块，如果无法按照输出的要求放置，会输出以下信息之一：

• Error: toy xxx is OUT OF BOARD!
• Error: toy xxx is overlapping some previously placed toy!

第一种信息表示有某个基块超出了边界，第二种信息表示某两个基块有重叠。

由于程序对于每个基块只按顺序处理一次，所以只报告与当前已经放置好的基块有重叠的基块。也就是说，第一个基块是不会被报第二种错误的。

第一种错误出现时，程序继续，伸出矩形之外的部分不予考虑；第二种错误出现时，程序继续，在重叠的地方以“!”标记。

检查程序的第二步是输出放置方案。位于矩形之外的部分不会画出，而重叠的地方用“!”标记。

检查程序的最后一步是输出汇总信息，有以下几种可能：

• Some toys are MISSING...
• Some toys are OUT OF BOARD...
• Some toys are overlapping some others...
• Correct! area = xxx

其中第一种信息表示有某个基块缺失，这是因为有基块的坐标 x 、y至少有一个为负。为了方便选手，本测试程序允许选手只放置部分基块观察结果，坐标中有负数的基块将被忽略，但是这在最后的评分程序中会被视为非法解。

特别提示：由于graduate_check输出摆放结果，每行可能会超过80个字符，行数也可能很多，建议采用重定向的方式把输出结果保存为文件，在编辑器中打开分析。命令为：graduate_check <测试点编号X> > result.txt