책상 위에 H행 W열의 직사각형 격자판이 있고, 격자판의 각 칸에는 동전이 하나씩 올려져있다. 위에서부터 i번째 행 (1 ≤ i ≤ H), 왼쪽으로부터 j번째 열(1 ≤ j ≤ W) 에 있는 동전의 처음 상태는, Si, j = #이면 앞면, Si, j = . 이면 뒷면이다.
A와 B는 이 동전들을 이용해 게임을 하려고 한다. 게임의 진행은 다음과 같다.
A가 원하는 행을 하나 고르고, 그 행에 있는 모든 동전을 뒤집는다.
B가 원하는 열을 하나 고르고, 그 열에 있는 모든 동전을 뒤집는다.
A는 앞면으로 놓여져 있는 모든 동전을 가져가고, B는 뒷면으로 놓여져 있는 모든 동전을 가져간다.
A와 B는 최대한 많은 동전을 가져가려고 한다.
게임이 시작될 때의 동전의 상태가 주어졌을 때, A와 B가 최선을 다하여 게임을 진행하였을 때 각각이 얻을 수 있는 동전의 개수를 구하여라.
ㅤ
입력
입력은 다음과 같은 형식을 갖는다.
ㅤ
출력
A와 B가 최선을 다해서 게임을 진행했을 때 각각이 얻을 수 있는 동전의 개수를 A, B 순으로 공백으로 구분하여 출력한다.
ㅤ
제한
H ≧ 1.
W ≧ 1.
H x W ≦ 500 000.
Si, j 는 # 또는 . 이다 (1 ≤ i ≤ H, 1 ≤ j ≤ W).
H 와 W는 양의 정수이다.
ㅤ
예제 1 설명
이 입력에서는 반드시 아래와 같이 게임이 진행된다.
A가 첫번째 행에 있는 모든 동전을 뒤집는다.
B가 첫번째 열에 있는 모든 동전을 뒤집는다.
이렇게 진행되면 게임판 위에 있는 동전 하나는 앞면 - 뒷면 - 앞면 순으로 변하게 된다. 따라서, A가 이 동전을 가져가고 B는 동전을 가져갈 수 없으므로 1, 0 을 공백으로 구분하여 출력한다.
ㅤ
예제 2 설명
A와 B가 최선을 다해서 게임을 진행하게 되면 A가 다섯번째 행을 뒤집고, B가 두번째 열을 뒤집는다. 게임의 진행과정은 아래와 같다.
cinador 3년 전
문제
책상 위에 H행 W열의 직사각형 격자판이 있고, 격자판의 각 칸에는 동전이 하나씩 올려져있다. 위에서부터 i번째 행 (1 ≤ i ≤ H), 왼쪽으로부터 j번째 열(1 ≤ j ≤ W) 에 있는 동전의 처음 상태는, Si, j = #이면 앞면, Si, j = . 이면 뒷면이다.
A와 B는 이 동전들을 이용해 게임을 하려고 한다. 게임의 진행은 다음과 같다.
A와 B는 최대한 많은 동전을 가져가려고 한다.
게임이 시작될 때의 동전의 상태가 주어졌을 때, A와 B가 최선을 다하여 게임을 진행하였을 때 각각이 얻을 수 있는 동전의 개수를 구하여라.
ㅤ
입력
입력은 다음과 같은 형식을 갖는다.
ㅤ
출력
A와 B가 최선을 다해서 게임을 진행했을 때 각각이 얻을 수 있는 동전의 개수를 A, B 순으로 공백으로 구분하여 출력한다.
ㅤ
제한
ㅤ
예제 1 설명
이 입력에서는 반드시 아래와 같이 게임이 진행된다.
이렇게 진행되면 게임판 위에 있는 동전 하나는 앞면 - 뒷면 - 앞면 순으로 변하게 된다. 따라서, A가 이 동전을 가져가고 B는 동전을 가져갈 수 없으므로 1, 0 을 공백으로 구분하여 출력한다.
ㅤ
예제 2 설명
A와 B가 최선을 다해서 게임을 진행하게 되면 A가 다섯번째 행을 뒤집고, B가 두번째 열을 뒤집는다. 게임의 진행과정은 아래와 같다.