Safe Company

Time limit5sMemory limit256 MB

Summary

Simulate a laser bouncing off / and \ mirrors on a huge grid, then decide whether one mirror inserted in a single empty cell can make the beam exit the bottom-right side, counting all such cells.

Level: Hard8 of 10
Topics: Simulation, Implementation, Math
Solved: No attempts yet

Problem

Safe Co. builds very secure safes. Their newest safe uses light: mirrors are placed on a rectangular grid and a laser is fired, and a detector checks whether the laser comes out.

The grid has $r$ rows and $c$ columns; rows are numbered $1$ to $r$ from top to bottom and columns $1$ to $c$ from left to right. The laser is fired into the left side of the top row, so it enters cell $(1, 1)$ travelling rightward. Whenever the beam enters a cell that holds a mirror it is reflected; every mirror is a 45-degree diagonal, either / or \. A / mirror turns a rightward beam upward and an upward beam rightward (and likewise a downward beam leftward); a \ mirror turns a rightward beam downward and a downward beam rightward (and likewise an upward beam leftward).

The safe opens exactly when the beam leaves the grid through the right side of the bottom row, that is, when it exits rightward out of cell $(r, c)$ . In every other case the alarm sounds.

Every safe is missing exactly one mirror: one grid cell that should hold a mirror is empty. To open the safe the user inserts a single mirror into one empty cell (the legitimate user knows the exact empty position and the mirror's shape).

A safe is called secure when it does not open with no mirror inserted, yet at least one choice of empty cell and mirror shape opens it. Given the current contents of a safe, report its status.

Input

The input contains several test cases; each describes one safe. The input ends at end of file.

The first line of a test case has four integers $r$ , $c$ , $m$ , $n$ ( $1 \le r, c \le 10^6$ , $0 \le m, n \le 2 \times 10^5$ ): the safe has $r$ rows and $c$ columns.

Each of the next $m$ lines has two integers $r_i$ and $c_i$ ( $1 \le r_i \le r$ , $1 \le c_i \le c$ ), meaning there is a / mirror at row $r_i$ , column $c_i$ .

Each of the following $n$ lines gives a \ mirror in the same format.

All $m + n$ positions are distinct.

Output

For each test case, print Case i: (with the test-case number $i$ ) followed by:

0 if the safe opens without inserting any mirror.
k r c if the safe does not open without a mirror, where $k$ is the number of empty cells at which inserting a mirror can open the safe, and $(r, c)$ is the lexicographically smallest such cell (smallest row first, then smallest column). A single cell counts once even if both a / and a \ mirror placed there would open the safe.
impossible if the safe cannot be opened even by inserting a mirror.

Examples1

Example 1

Input

5 6 1 4
2 3
1 2
2 5
4 2
5 5
100 100 0 2
1 77
100 77
100 100 0 0

Expected output

Case 1: 2 4 3
Case 2: 0
Case 3: impossible