1510_超级象限树

Alice一岁九个月了，昨天她开始研究"象限树"。象限树是一种用来存储数字图像的数据结构。目前Alice要处理的只是简单的位图，是由黑白两色组成的，黑色像素用1表示，白色像素用0表示。

用象限树表示一幅位图的规则是：用根节点来统领整幅图。如果整幅图都是1或者都是0，那么把该值存入该节点即可。否则，把这幅图切分为大小相同的四个象限（四副子图），根节点添加四个子节点，这四个子节点分别代表这四个象限，具体是：第一个子节点代表左上象限，第二个子节点代表右上象限，第三个子节点代表左下象限，第四个子节点代表右下象限。递归把以上规则应用到这四个子树上。例如，图1左边是一幅4x4像素的图片，就用右边的象限树来表示。

图1

注意，这种做法只适应于这种情况：图片是正方形的，且图片的边长是2的整数幂。对于不满足这个形状的图片，Alice就在图片的右侧的列和下方的行补充0，使它的边长满足条件。例如，对于一幅5x13的图片，Alice就把它扩充成为一幅16x16的位图（原图位于新图的左上方，其余都用0来填充）。

Alice发现使用象限树来存储图片可以节省大量空间，Alice进一步发现，如果能够处理重复出现的子树，那么就可以节省更多的存储空间。例如，图1的象限树中，根的第一棵子树和第三棵子树是相同的，因此可以把指向第三棵子树的指针也指向第一棵子树，就可以得到图2的树：

图2

Alice把这种压缩的象限树称为"超级象限树"。只有当象限树的高度大于等于1时（即至少有2层），使用指针来节省存储空间的方法才有效。因此，把图2中右边的5个B都指向最左边的B，实际上是不能压缩节省空间的。采用以上规则，超级象限树有12个节点，少于原象限树的17个节点。

Alice交一个任务给你：采用以上方法来表示一些图片，当采用象限树和超级象限树来存储的时候，分别有多少个节点。

输入有多个测试用例。

每个测试用例的第一行是两个整数n和m，表示这幅图片像素的行数和列数。n和m不超过128。接下来n行，每行m个字符，表示这幅图片。黑色像素用1表示，白色像素用0表示。

最后一行0 0表示输入结束（图片是0行0列），这行不用处理。

对每个测试用例，输出两个整数，用一个空格分隔它们。第一个数是用象限树表示这幅图片时所需的节点数，第二个数是用超级象限树表示时所需的节点数。

4 4
1011
0111
1010
0111
6 7
1110111
1010101
0000000
0100010
1011101
1010101
0 0

17 12
61 24