TYVJ Qixi Festival Booth Arrangement

During the Qixi Festival, inspired by the legend of the Cowherd and the Weaver Girl, TYVJ is hosting an offline celebration. The festival area is organized as a rectangular grid of booths with N rows and M columns (i.e. a total of N×M booths). Some of the booths are of particular interest to cl (for example, takoyaki, candied apple, cotton candy, shooting games, etc.).

Vani has contacted the organizer zhq to re-arrange the booths, aiming to fulfill two conditions simultaneously:

1. All rows have the same number of interesting booths.
2. All columns have the same number of interesting booths.

However, zhq informs Vani that the booths have already been placed arbitrarily, and the only allowed adjustment is to swap two adjacent booths. Two booths are considered adjacent if and only if they are in adjacent positions in the same row or the same column. Owing to the TYVJ development team’s miraculous twist of space, the first and last positions in each row or column are also considered adjacent (i.e. the grid is cyclic both horizontally and vertically).

Vani now wonders: What is the maximum number of these two conditions that can be satisfied by rearranging the booths, and under that maximum, what is the minimum number of swaps needed?

Note that, if the total number of interesting booths is denoted as T, then to satisfy the conditions for all rows and columns simultaneously one must have

\(T\equiv 0 \; (\bmod\; N)\) and \(T\equiv 0 \; (\bmod\; M)\),

so that the target number of interesting booths for each row is \(r=\frac{T}{N}\) and for each column is \(c=\frac{T}{M}\). If both conditions cannot be simultaneously achieved, at least one of them may be possible if either \(T\equiv 0 \; (\bmod\; N)\) or \(T\equiv 0 \; (\bmod\; M)\).

The cost (i.e. the minimum number of swaps) is determined by the minimal moves needed to re-balance the counts along rows and/or columns. For a particular dimension (say rows), let a[i] be the count of interesting booths in row i and set the difference d[i]=a[i]-r. By traversing the rows in cyclic order, one may compute a prefix sum array \(p\) (with \(p[0]=0\)) such that \(p[i]=d[0]+d[1]+\cdots+d[i-1]\) for \(1\le i\le N\). The minimal number of swaps needed to balance the rows is given by \(\sum_{i=0}^{N-1}|p[i]-m|\), where \(m\) is the median of the prefix sums. An analogous process is applied to the columns if needed. The final answer is computed as follows:

• If both row and column conditions can be achieved (i.e. \(T\equiv 0 \; (\bmod\; N)\) and \(T\equiv 0 \; (\bmod\; M)\)), then the answer is 2 and the minimum swaps equals the sum of the minimal vertical (row) swaps and horizontal (column) swaps.
• If only one condition (either row or column) is achievable, then the answer is 1 and the minimum swaps is the corresponding cost for that dimension.
• If neither condition can be satisfied, then the answer is 0 and no swaps are required.

It is guaranteed that swapping adjacent booths (with cyclic adjacency) is sufficient to achieve the best possible arrangement.

inputFormat

The input begins with a line containing two integers N and M (the number of rows and columns, respectively).

Then follow N lines, each containing M integers. Each integer is either 0 or 1, where 1 indicates a booth that is of interest to cl, and 0 indicates otherwise.

It is guaranteed that N and M are positive integers.

outputFormat

Output two space‐separated integers on a single line. The first integer is the maximum number of conditions (row uniformity and/or column uniformity) that can be satisfied by an appropriate sequence of swaps (this number can be 0, 1, or 2). The second integer is the minimum number of swaps required to achieve that arrangement.

sample

3 3
1 0 0
0 1 0
0 0 1

2 0