This page is still under construction.

Parts of this page are still being built. What you see may change.

Tracking Bio-bots

Time limit2sMemory limit1024 MB

Summary
Given a grid room with horizontal walls, count the squares from which a robot moving only north or east can never reach the northeast exit.
Level

Medium6 of 10

Topics
Intervals, Sorting, Simulation
Solved
No attempts yet

Problem

The researchers at International Bio-bot Makers (IBM) have invented a new kind of Bio-bot, a robot with behavior that mimics biological organisms. The robot is still in an early stage of development, and the current models are similar to simple four-wheeled rovers. Like most modern robots, Bio-bots are not very mobile. Their weak motors and limited turning capability restrict their movement considerably, even in simple environments with few obstacles.

Bio-bots currently operate in a room shaped like an m×nm \times n grid. The exit is in the northeast corner, and the room slopes down toward it. A Bio-bot can therefore move only north or east at any time. Some squares in the room are occupied by walls, which completely block the robot.

In Figure 1, a Bio-bot on square A can leave the room, but a Bio-bot on square B is trapped inside no matter what it does. Squares like B are called "stuck squares." (Walls are not stuck squares.) Given the description of a room, count the total number of stuck squares in the room.

Input

Input consists of multiple test cases, each describing one room. The first line of a test case has three integers m, n, and w (1≤m,n≤1061 \le m, n \le 10^6, 0≤w≤10000 \le w \le 1000). They give the number of rows, the number of columns, and the number of horizontal walls in the room.

Each of the next w lines has four integers x1, y1, x2, y2, the coordinates of the squares at the two ends of one wall. All walls run from west to east, so 0≤x1≤x2<n0 \le x_1 \le x_2 < n and 0≤y1=y2<m0 \le y_1 = y_2 < m. Walls do not overlap. The southwest corner of the room is at (0,0), and the northeast corner is at (n-1, m-1).

The last test case is followed by a line containing 0 0 0.

Output

For each test case, print one line in the form "Case k: s", where k is the test case number and s is the number of stuck squares in that room.

Examples1

  1. Example 1

    Input
    8 8 3
1 6 3 6
2 4 2 4
4 2 7 2
0 0 0
    Expected output
    Case 1: 8