Bio-bot 추적

IBM(International Bio-bot Makers)의 연구원들이 생물의 행동을 흉내 내는 새로운 종류의 Bio-bot을 발명했다. 이 로봇은 아직 개발 초기 단계에 있어서, 현재 모델은 단순한 4륜 로버와 비슷하다. 대부분의 현대 로봇처럼 Bio-bot도 이동성이 높지 않다. 모터 출력이 약하고 회전 능력도 제한되어 있어, 장애물이 적은 단순한 환경에서도 움직임이 크게 제약된다.

Bio-bot은 현재 $m \times n$ 격자 모양의 방에서 작동한다. 출구는 북동쪽 모서리에 있고, 방은 출구를 향해 기울어 내려간다. 따라서 Bio-bot은 언제든 북쪽이나 동쪽으로만 이동할 수 있다. 방의 일부 칸에는 벽이 있으며, 벽은 로봇을 완전히 막는다.

그림 1에서 A 칸에 있는 Bio-bot은 방을 빠져나갈 수 있다. 반면 B 칸에 있는 Bio-bot은 어떻게 움직여도 방 안에 갇힌다. B와 같은 칸을 "갇힌 칸"이라고 부른다. (벽은 갇힌 칸이 아니다.) 방의 설명이 주어졌을 때, 방에 있는 갇힌 칸의 총 개수를 구하라.

입력은 여러 개의 테스트 케이스로 이루어지며, 각 테스트 케이스는 방 하나를 설명한다. 테스트 케이스의 첫 줄에는 정수 m, n, w ($1 \le m, n \le 10^6$, $0 \le w \le 1000$)가 주어진다. 각각 방의 행 수, 열 수, 가로 방향 벽의 수이다.

다음 w줄에는 벽 하나의 양 끝 칸 좌표 x1, y1, x2, y2가 주어진다. 모든 벽은 서에서 동으로 놓여 있으므로 $0 \le x_1 \le x_2 < n$, $0 \le y_1 = y_2 < m$이다. 벽끼리는 겹치지 않는다. 방의 남서쪽 모서리는 (0,0), 북동쪽 모서리는 (n-1, m-1)이다.

마지막 테스트 케이스 다음 줄에는 0 0 0이 주어진다.

각 테스트 케이스마다 "Case k: s" 형식으로 한 줄을 출력한다. k는 테스트 케이스 번호이고, s는 그 방에 있는 갇힌 칸의 수이다.