SPOJ Brasil

Você irá construir uma nova fábrica na sua cidade. Já que você necessida de muita energia elétrica, ter a fábrica posicionada perto de uma estação de força é importante. Você quer construir uma lista priorizada das possíveis localizações.

A área onde a fábrica precisa ser construída pode ser representada como uma grade retangular de N linhas e M colunas de células. Algumas dessas células contem uma estação de força. A nova fábrica ocupa exatamente uma célula, e pode ser construída em qualquer célula livre (ou seja, qualquer célula que não contém uma estação de força).

Numerando as linhas de 1 até N e as colunas de 1 até M, a localização de uma célula pode ser descrita por dois inteiros. A célula ( i , j ) é a célula na linha i e coluna j. A distância entre as células (i₀,j₀) e (i₁,j₁) é max( |i₀ - i₁| , |j₀ - j₁| ) onde | x | representa o valor absoluto de x. A prioridade elétrica de uma localização é a menor distância até qualquer estação de força.

Com isso em mente, você vai numerar todas as possíveis localizações com inteiros consecutivos começando de 1. Você fará isso em ordem crescente de prioridade elétrica. Dentre locais com a mesma prioridade elétrica, você vai numerá-los em ordem crescente de seu índices de linha. Dentre locais com mesmas prioridade elétrica e índice de linha, você vai listá-los em ordem crescente de seu índices de coluna.

Na figura abaixo você pode ver uma grade 4 x 7. Células pretas são as células onde há uma estação de força. Células cinza escuras possuem prioridade elétrica 1, cinza claras prioridade elétrica 2 e células brancas prioridade elétrica 3. O número dentro de cada célula é o número atribuído por você à célula.

Você receberá inúmeras consultas sobre a lista construída. Em cada consulta será dado um número representando a posição na lista final e você deverá dizer a qual célula foi atribuída a posição dada.

Entrada

Cada caso de teste se estende por várias linhas. A primeira linha contém três inteiros N, M e P, representando o número de linhas e colunas da grade (1 ≤ N,M ≤ 10⁹) e o número de estações de força (1 ≤ P ≤ 20). Cada uma das P linhas seguintes contém dois inteiros R e C representando a linha e a coluna de uma estação de força (1 ≤ R ≤ N e 1 ≤ C ≤ M). Em cada caso de teste, todas as estações de força estão em células distintas. A próxima linha contém um único inteiro Q representando o número de consultas (1 ≤ Q ≤ 50). Então segue uma linha com Q inteiros p₁, ... , p_Q representando as posições da lista priorizada (1 ≤ p_i ≤ N x M - P).

O último caso de teste é seguido de uma linha contendo três zeros.

Saída

Para cada caso de teste, imprima Q+1 linhas. A linha i das primeiras Q linhas devem conter dois inteiros representando a linha e a coluna da localização que foi atribuída ao número pi. A última linha de cada caso deve conter um único caractere '-' (hífen).

Exemplo

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

Saída:
1 4
3 3
4 5
2 7
4 7
4 1
-
1000000000 1000000000
-