단조로운 초콜릿
시간 제한9초메모리 제한512 MB
흰 초콜릿 칸이 최대 1000개인 매우 큰 격자에서, 흰 칸 개수가 홀수인 접두 직사각형과 짝수인 접두 직사각형의 수를 각각 센다.
문제
Fouad는 초콜릿을 먹고 싶어서 N행 M열의 직사각형 초콜릿을 샀다.
이 초콜릿의 대부분의 칸은 다크 초콜릿이고, K개의 칸만 화이트 초콜릿이다. Fouad는 이 초콜릿의 접두 부분 격자를 먹으려고 한다. 접두 부분 격자란 첫 번째 칸 (1, 1)에서 시작하여 임의의 칸 (i, j)에서 끝나는 직사각형 부분 격자이다. Fouad는 또한 완벽한 접두 부분 격자가 몇 개인지 궁금해한다. 완벽한 접두 부분 격자란 화이트 초콜릿 칸을 홀수 개 포함하는 부분 격자이다.
Fouad가 완벽한 접두 부분 격자와 완벽하지 않은 접두 부분 격자의 개수를 구할 수 있도록 도와주자.
입력
입력의 첫 줄에는 테스트 케이스의 수를 나타내는 정수 T가 주어진다.
각 테스트 케이스는 세 정수 N, M, K (1 ≤ N, M ≤ 109, 0 ≤ K ≤ 103)가 있는 한 줄로 시작한다. N과 M은 각각 초콜릿의 행과 열의 수이고, K는 화이트 초콜릿 칸의 수이다.
그다음 K개의 줄이 이어지며, 각 줄에는 두 정수 Xi와 Yi (1 ≤ Xi ≤ N, 1 ≤ Yi ≤ M)가 주어져 화이트 초콜릿 칸의 위치를 나타낸다. 주어진 모든 위치는 서로 다름이 보장된다.
출력
각 테스트 케이스마다 완벽한 접두 부분 격자의 개수와 완벽하지 않은 접두 부분 격자의 개수를 각각 나타내는 두 정수를 공백으로 구분하여 한 줄에 출력한다.
힌트
두 번째 테스트 케이스에서 초콜릿은 다음과 같이 나타낼 수 있다:
ddd
dwd
ddd
여기서 'd'는 다크 초콜릿 칸을, 'w'는 화이트 초콜릿 칸을 나타낸다. 다음 칸에서 끝나는 네 개의 완벽한 접두 부분 격자가 있다: (2, 2), (2, 3), (3, 2), (3, 3).