Coin Collecting 2

Problem Statement

Coins are arranged on a table in a rectangular grid of H rows and W columns. Initially, for the coin in row i from the top (1 ≦ i ≦ H) and column j from the left (1 ≦ j ≦ W), the heads side is visible if S_i,j= #, and the tails side is visible if S_i,j= ..

Aoi and Rin decide to play a game using these coins. The game proceeds as follows.

1. Aoi chooses one row and flips all the coins in that row.
2. Rin chooses one column and flips all the coins in that column.
3. Aoi collects all coins showing heads, and Rin collects all coins showing tails.

Both Aoi and Rin want to collect as many coins as possible.

Given the initial state of the coins, write a program that determines the number of coins each player can collect when both play optimally.

Constraints

• H ≧ 1.
• W ≧ 1.
• H × W ≦ 500000.
• S_{i, j} is either # or . (1 ≦ i ≦ H, 1 ≦ j ≦ W).
• H, W are integers.

Input

The input is given in the following format.
H W
S_1,1 S_1,2 … S_1,W
S_2,1 S_2,2 … S_2,W
︙
S_H,1 S_H,2 … S_H,W

Output

Output the scores of Aoi and Rin in this order, separated by a space.

Sample Input and Output

Sample Input 1

1 1
#

Sample Output 1

1 0

In this sample input, the game always proceeds as follows.

1. First, Aoi flips all the coins in row 1.
2. Next, Rin flips all the coins in column 1.

The visible side of the only coin changes from "heads → tails → heads", so Aoi can collect 1 coin, while Rin cannot collect any coins. Therefore, output 1 and 0 in this order, separated by a space.

Sample Input 2

5 5
#####
####.
###..
##...
#....

Sample Output 2

13 12

An example of the game progression when both players play optimally is shown in the figure below.

---

Sample Input 3

1 40
..........##########..........##########

Sample Output 3

19 21

Sample Input 4

7 1
#
#
#
#
#
#
#

Sample Output 4

1 6

Sample Input 5

5 5
.###.
...##
..##.
.##..
##...

Sample Output 5

11 14

Sample Input 6

10 40
........................................
..######.....####.....#####.....####....
.....#......#....#......#......#........
.....#......#....#......#......#........
.....#......#....#......#......#........
.....#......#....#......#......#..####..
..#..#......#....#......#......#....#...
..#..#......#....#......#......#....#...
...##........####.....#####.....####....
........................................

Sample Output 6

104 296

---