Virus

Time Limit: 5 Seconds    Memory Limit: 32768 KB

Sunny Cup 2003 - Preliminary Round

April 20th, 12:00 - 17:00

Problem D: Virus

Recently a new virus was fast spreading in the country. Many cities got infected. Biologists have already located the source of the virus, now you're going to help them determine the area of infected regions.

The country is laid out as a grid of squares on a rectangle, each city occupies one square. Some squares are occupied by wasteland which would block the virus. The whole country is surrounded by the sea which would also block the virus. Two squares are adjacent only if they share a common edge. The virus can only spread from one square to its adjacent ones. The distance between two squares equals to the minimum number of squares the virus needs to travel from one to another. Once the virus is blocked, it will stop spreading to all the squares to which the distance from the source equals to the blocked square. Virus from different sources will not interfere with each other.

Here's an illustration of how the virus spread:

Figure 1: Virus originate from (4,4) and (7,7) with wasteland at (2,2) and (3,2)

Another illustration:

Figure 2: Virus originate from (2,2), (2,4) and (2,6) with wasteland at (1,6) and (3,6)

Given a map description and the positions of the virus sources, your job is to figure out the number of infected regions and their total area.

Input

The input consists of several test cases. Each begins with 4 integers n m b s on a line, which representing the number of rows of the country, the number of columns, the number of rectangular wastelands and the number of virus sources respectively. The following b lines each contains 4 integers x1 y1 x2 y2 describes the upper-left corner and the lower-right corner of the wasteland. The next s lines each contains two integers x y which is the position of the source of the virus. The input is terminated by 4 zeros.

Constraints: 1 <= n <= 10000, 1 <= m <= 10000, 0 <= b <= 200, 1 <= s <= 200

With coordinates: 1 <= x <= n, 1 <= y <= m

The virus source will never be in the wasteland or out of bound.

Output

For each test case, print out two lines. The first line contains the case number and the second contains a message "There are x infected regions with total area of xxx", if there's only one infected region then use "is" and "region" in the above message instead.

Print a blank line between cases.

Sample Input

8 8 1 2
2 2 3 2
4 4 
7 7
3 6 2 3
1 6 1 6
3 6 3 6
2 2
2 4
2 6
0 0 0 0

Sample Output

Case 1:
There are 2 infected regions with total area of 18

Case 2:
There is 1 infected region with total area of 10

Submit

Source: Zhejiang University Local Contest 2003, Preliminary