This page is still under construction.

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

This Too Shall Pass

Time limit3sMemory limit256 MB

Summary
Find every teammate joined to player 1 by a straight segment that touches no guarded square.
Level

Medium4 of 10

Topics
Geometry, Brute force
Solved
No attempts yet

Problem

A soccer field is drawn as a grid with rr rows and cc columns. Every player takes up one grid square, and the oo offensive players and the dd defensive players all stand on different squares. The offensive players are numbered from 1 in the order they appear in the input, and player 1 has the ball.

A defender can step to a neighboring square to intercept a pass, so one defender guards the square he stands on plus the eight squares that meet it along a side or at a corner, nine squares in all. Squares that fall outside the grid are not counted. Guarded areas of different defenders may overlap.

Player kk is open when the segment that joins the center of player 1's square to the center of player kk's square touches no guarded square at any point. Grazing a single corner point of a guarded square is enough for the pass to be intercepted. If a defender guards player 1's own square or the receiver's square, an endpoint of the segment already lies inside a guarded square, so that pass is not open. Offensive players never block a pass to another offensive player.

Find every offensive player that player 1 can pass to.

Input

The input holds several test cases.

The first line of each test case holds four integers rr, cc, oo, dd separated by spaces: the number of rows, the number of columns, the number of offensive players, and the number of defensive players. (1≤r≤501 \le r \le 50, 1≤c≤501 \le c \le 50, 1≤o1 \le o, 0≤d0 \le d, o+d≤r×co + d \le r \times c)

The next oo lines each hold the row and the column of one offensive player. Rows and columns are numbered from 0, so a row number is less than rr and a column number is less than cc. The next dd lines hold the defenders in the same format. No two players stand on the same square.

The offensive players are numbered from 1 in the order given, and player 1 has the ball.

A line reading 0 0 0 0 ends the input. That line is not a test case.

Output

For each test case, print Case x: on one line, then the numbers of the offensive players that player 1 can pass to, in increasing order. Put one space in front of each number. xx is the test case number counted from 1.

If no player is open, print Case x: with nothing after it.

Examples8

  1. Example 1

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

  2. Example 2

    Input
    9 9 2 1
8 0
0 8
5 6
9 9 2 1
8 0
0 8
6 6
0 0 0 0
    Expected output
    Case 1:
Case 2: 2

  3. Example 3

    Input
    5 5 3 1
2 2
0 0
4 4
1 2
5 5 3 1
0 0
4 4
0 4
3 3
0 0 0 0
    Expected output
    Case 1:
Case 2: 3

  4. Example 4

    Input
    1 1 1 0
0 0
1 2 2 0
0 0
0 1
2 2 2 1
0 0
1 1
0 1
3 3 2 1
0 0
2 2
2 0
0 0 0 0
    Expected output
    Case 1:
Case 2: 2
Case 3:
Case 4:

  5. Example 5

    Input
    1 50 3 1
0 0
0 49
0 20
0 30
1 50 2 1
0 0
0 10
0 40
0 0 0 0
    Expected output
    Case 1: 3
Case 2: 2

  6. Example 6

    Input
    50 1 3 1
0 0
49 0
10 0
25 0
50 1 2 0
49 0
48 0
0 0 0 0
    Expected output
    Case 1: 3
Case 2: 2

  7. Example 7

    Input
    6 6 3 2
0 2
5 2
2 5
0 0
5 5
0 0 0 0
    Expected output
    Case 1: 2 3

  8. Example 8

    Input
    10 11 4 7
5 0
5 10
0 10
9 10
0 5
1 5
2 5
3 5
7 5
8 5
9 5
0 0 0 0
    Expected output
    Case 1: 2