Electric Needs

You are building a new factory in your city. Because the factory has large electric needs, placing it close to a power plant matters, so you want to produce a prioritized list of the possible locations.

The candidate area is a rectangular grid of $N$ rows and $M$ columns of cells. Some cells contain a power plant. The factory occupies exactly one cell and may be placed on any empty cell (any cell that does not contain a power plant).

Rows are numbered $1$ to $N$ and columns $1$ to $M$, so a cell is identified by two integers: cell $(i, j)$ is in row $i$ and column $j$. The distance between cells $(i_0, j_0)$ and $(i_1, j_1)$ is $\max(|i_0 - i_1|, |j_0 - j_1|)$, where $|x|$ is the absolute value of $x$. The electric priority of a location is its minimum distance to a power plant.

Number every possible location with consecutive integers starting from $1$, in ascending order of electric priority. Among locations with equal electric priority, order them by ascending row number; among those with equal priority and row, order them by ascending column number.

For intuition, in a $4 \times 7$ grid the empty cells that lie at distance $1$ from a power plant all receive electric priority $1$, the next ring outward receives priority $2$, and so on; the empty cells are then numbered following the ordering rule above.

You will answer several queries about this prioritized list. Each query gives a position in the list, and you must report which location was assigned that position.

The input contains several test cases.

Each test case begins with a line of three integers $N$, $M$ and $P$ — the number of rows, the number of columns ($1 \le N, M \le 10^9$), and the number of power plants ($1 \le P \le 20$). Each of the next $P$ lines contains two integers $R$ and $C$, the row and column of a power plant ($1 \le R \le N$, $1 \le C \le M$). Within a test case all power plant locations are distinct. The next line contains one integer $Q$, the number of queries ($1 \le Q \le 50$). The following line contains $Q$ integers $p_1, \dots, p_Q$, positions in the prioritized list ($1 \le p_i \le N \times M - P$).

The last test case is followed by a line containing three zeros (0 0 0), which must not be processed.

For each test case, output $Q + 1$ lines. For $i = 1, \dots, Q$, line $i$ contains two integers: the row and the column of the location that was assigned position $p_i$. After those $Q$ lines, print a single line containing the character - (a hyphen).