Image Compression

An image made only of white and black pixels can be represented by a quadtree. The root of the quadtree represents the entire image. If a region has only one color, it is represented by one vertex for that color. Otherwise, the region is split into four equal-sized regions, and the four child vertices represent the upper-left, upper-right, lower-left, and lower-right regions in that order. The same rule is applied recursively to each child region.

The image may not be square, and its side lengths may not be powers of two. In that case, place the original image in the upper-left corner and fill cells to the right and below with white pixels until the image becomes a square. The side length of this square is the smallest power of two that is at least both original dimensions. For example, a 5 x 13 image is expanded to 16 x 16, and every added cell is white.

A quadtree is already a compressed representation, but it can be reduced further: if identical subtrees appear more than once, store that subtree only once and connect the other occurrences with pointers. Two subtrees are identical when their tree shape and color placement are the same, even if the actual regions they represent have different sizes.

However, a B or W vertex that represents a single color is a value, not a pointer target for compression. Therefore, one-vertex trees are not merged when counting the compressed size; identical single-color vertices are still counted separately where they appear.

Given an image, compute the number of vertices in its ordinary quadtree and the minimum possible number of vertices after applying this subtree sharing rule.

The first line contains two integers n and m, the dimensions of the image. Both n and m are between 1 and 128 inclusive, and the image has size n x m.

Each of the next n lines contains a string of length m. Each character is either 0 or 1; 0 means white and 1 means black.

Print two integers separated by a space: the number of vertices in the ordinary quadtree and the minimum number of vertices in the most efficiently compressed quadtree.