コイン集め 2 (Coin Collecting 2)

問題文

机の上に，縦 H 行，横 W 列の長方形状にコインが並べられている． 最初，上から i 行目 (1 ≦ i ≦ H)，左から j 列目 (1 ≦ j ≦ W) のコインは， S_i,j= # のとき表面，S_i,j= . のとき裏面が見えている状態である．

葵と凛は，これらのコインを用いてゲームを行うことにした．ゲームは以下のような流れで行われる．

1. 葵がどれか 1 つの行を選び，その行のコインをすべてひっくり返す．
2. 凛がどれか 1 つの列を選び，その列のコインをすべてひっくり返す．
3. 葵が，表面が見えるコインをすべて獲得する．また凛が，裏面が見えるコインをすべて獲得する．

葵と凛はそれぞれ，できるだけ多くのコインを獲得したい．

ゲーム開始時のコインの状態が与えられたとき， 両者が最善を尽くした場合にそれぞれが獲得できるコインの枚数を求めるプログラムを作成せよ．

制約

• H ≧ 1．
• W ≧ 1．
• H × W ≦ 500000．
• S_{i, j} は #，. のいずれかである (1 ≦ i ≦ H，1 ≦ j ≦ W)．
• H, W は整数である．

入力

入力は以下の形式で与えられる．
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

出力

葵と凛の得点をこの順に空白区切りで出力せよ．

入出力例

入力例 1

1 1
#

出力例 1

1 0

この入力例では，必ず以下のようにゲームが進行する．

1. まず，葵が 1 行目のすべてのコインをひっくり返す．
2. 次に，凛が 1 列目のすべてのコインをひっくり返す．

このとき，唯一のコインの見える面は「表→裏→表」と変化するため，葵が 1 枚のコインを獲得できるが，凛はコインを獲得できない．したがって，1，0 をこの順に空白区切りで出力する．

入力例 2

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

出力例 2

13 12

両者が最善を尽くした場合の，ゲームの進行の一例を下図に示す．

---

入力例 3

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

出力例 3

19 21

入力例 4

7 1
#
#
#
#
#
#
#

出力例 4

1 6

入力例 5

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

出力例 5

11 14

入力例 6

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

出力例 6

104 296

---