Electric Needs

Time Limit: 1 Second    Memory Limit: 65536 KB

You are going to construct a new factory in your city. Since you have major electric needs, having the factory placed close to a power plant is important. You want to build a prioritized list of possible locations.

The area in which the factory needs to be located can be represented as a rectangular grid of N rows and M columns of cells. Some of those cells contain a power plant. The new factory occupies exactly one cell, and can be placed in any empty cell (i.e., any cell that does not contain a power plant).

Numbering rows from 1 to N and columns from 1 to M, the location of a cell can be described by two integers. Cell (i, j) is the cell in row i and column j. The distance between cell (i₀, j₀) and cell (i₁, j₁) is max(|i₀ − i₁|, |j₀ − j₁|) where |x| represents the absolute value of x. The electric priority of a location is its minimum distance to a power plant. With this in mind, you will number all possible locations with consecutive integers starting from 1. You will do it in ascending order of electric priority. Among locations with the same electric priority, you will number them in ascending order of their row numbers. Among locations with the same electric priority and row number, you will list them in ascending order of column numbers.

In the following picture you can see a 4 × 7 grid. Black cells are the cells in which there is a power plant. Dark gray cells have an electric priority of 1, light gray cells an electric priority of 2 and white cells an electric priority of 3. The number inside each cell is the number assigned by you to the location.

You will receive several queries about the prioritized list built. In each query you will be given a number representing a position in the prioritized list and you have to calculate which location was assigned the given position.

 

Input

Each test case is given using several lines. The first line contains three integers N, M and P, representing the number of rows and columns of the grid (1 ≤ N,M ≤ 10⁹) and the number of existing power plants (1 ≤ P ≤ 20). Each of the next P lines contains two integers R and C representing the row and column numbers of the location of a power plant (1 ≤ R ≤ N and 1 ≤ C ≤ M). Within each test case, all power plant locations are different. The next line contains a single integer Q representing the number of queries (1 ≤ Q ≤ 50). Then follows a line with Q integers p₁, ..., p_Q representing positions in the prioritized list (1 ≤ p_i ≤ N×M−P).

The last test case is followed by a line containing three zeros.

Output

For each test case output Q + 1 lines. Line i of the first Q lines must contain two integers representing the row and column numbers of the location that was assigned number pi. The last line for each test case must contain a single character ‘-’ (hyphen).

Sample Input

4 7 2
2 5
4 4
6
1 6 11 16 21 26
1000000000 1000000000 1
1 1
1
999999999999999999
0 0 0

Sample Output

1 4
3 3
4 5
2 7
4 7
4 1
-
1000000000 1000000000
-

Submit

Source: Latin American Regional Contest 2010