직사각형 뒤집기 2

팡 교수는 던전의 함정 방에 들어간다. 이 방은 $n \times m$ 크기의 체스판으로 나타낼 수 있다. $(i, j)$ ($1\le i\le n$, $1\le j\le m$)는 $i$행 $j$열의 칸을 뜻한다. 매초 칸 하나의 바닥이 부서져서, 팡 교수는 그 칸에 더 이상 설 수 없다. $nm$초가 지나면 설 수 있는 칸이 남지 않아 팡 교수는 더 깊고 위험한 다음 층으로 떨어진다.

하지만 팡 교수는 침착함이 어떤 어려움이든 이겨내는 열쇠라는 것을 안다. 그래서 당황하는 대신, 매초가 지난 뒤에도 모든 칸이 부서지지 않은 직사각형의 개수를 센다. 네 정수 $a, b, c, d$ ($1\le a\le b\le n$, $1\le c\le d\le m$)로 주어지는 직사각형은 $a\le i\le b$이고 $c\le j\le d$인 모든 칸 $(i, j)$를 포함한다. 직사각형은 모두 $\frac{n(n+1)}{2} \times \frac{m(m+1)}{2}$개이다.

첫 줄에 공백으로 구분된 두 정수 $n$, $m$ ($1\le n, m\le 500$)이 주어진다. $(i+1)$번째 줄에는 공백으로 구분된 두 정수 $a$, $b$가 주어지며, 이는 칸 $(a, b)$가 $i$초에 부서진다는 뜻이다. 각 칸은 입력에 정확히 한 번씩 나타난다.

$nm$개의 줄을 출력한다. $i$번째 줄에는 처음 $i$개의 칸이 부서진 뒤에도 모든 칸이 부서지지 않은 직사각형의 개수를 출력한다.

예시에서 1초 뒤에는 조건을 만족하는 넓이 1 직사각형이 3개, 넓이 2 직사각형이 2개 있으므로 첫 줄은 5이다. 2초 뒤에는 2열의 칸만 남으므로 답은 3이다. 3초 뒤에는 칸 하나만 남으므로 답은 1이다. 4초 뒤에는 모든 칸이 부서지므로 답은 0이다.