이진 표

면접 대비

시간 제한6초메모리 제한1024 MB

요약

이진 표에 직사각형 뒤집기를 적용할 때마다, 왼쪽 위 모서리에서 시작하는 직사각형 뒤집기로 표를 모두 0으로 만드는 최소 횟수를 구합니다.

난이도: 보통10점 중 6점
유형: 행렬, 누적 합
정답자: 아직 제출이 없습니다

문제

$n$ 개의 행과 $m$ 개의 열로 이루어진 표 $A$ 가 있다. 표의 각 칸에는 0 또는 1을 적을 수 있다. 행은 위에서 아래로 $1, \ldots, n$ 번, 열은 왼쪽에서 오른쪽으로 $1, \ldots, m$ 번 번호를 붙이며, $i$ 번째 행과 $j$ 번째 열에 있는 칸의 좌표는 $(i, j)$ 이다. 아래 그림도 참고한다.

표에서 연산을 수행할 수 있다. 연산은 네 수 $i_1, j_1, i_2, j_2$ 로 주어진다. 대각선 방향의 두 꼭짓점이 $(i_1, j_1)$ 과 $(i_2, j_2)$ 인 직사각형에 속한 칸을 모두 고른 뒤, 각 칸의 값을 바꾼다. 0은 1로, 1은 0으로 바꾼다.

직사각형의 왼쪽 위 꼭짓점이 표의 왼쪽 위 꼭짓점과 같은 연산, 즉 $i_1 = j_1 = 1$ 인 연산을 간단한 연산이라고 한다.

처음에는 표의 모든 수가 0이다. 이후 표를 바꾸는 연산을 $q$ 번 수행한다. 연산을 수행할 때마다, 표의 모든 수를 다시 0으로 만들기 위해 간단한 연산을 추가로 몇 번 해야 하는지 구한다.

입력

첫 줄에 세 정수 $n$ , $m$ , $q$ 가 주어진다 ( $1 \le n, m \le 1000$ , $1 \le q \le 100000$ ). 표의 크기와 연산의 개수이다.

이후 $q$ 개의 줄에 각각 연산을 나타내는 네 정수 $i_1$ , $j_1$ , $i_2$ , $j_2$ 가 주어진다 ( $1 \le i_1 \le i_2 \le n$ , $1 \le j_1 \le j_2 \le m$ ).

출력

$q$ 개의 줄을 출력한다. $i$ 번째 줄에는 입력의 처음 $i$ 개 연산을 수행한 뒤, 표의 모든 수를 0으로 만드는 데 필요한 간단한 연산의 최소 횟수를 출력한다.

힌트

아래 그림의 윗줄은 입력의 세 연산을 차례로 수행한 뒤의 표 $A$ 이다. 각 열은 최소 횟수의 간단한 연산으로 표를 0으로 되돌리는 과정을 보여준다.

예제1

예제 1
입력
```
2 3 3
1 2 2 2
1 1 2 1
1 2 1 3
```
예상 출력
```
2
1
3
```