SPOJ Brasil

A internet oferece uma variedade de facilidades interativas para mapas, de tal forma que os usuários podem ter uma visão geral de uma região geográfica ou podem fazer zoom para uma rua específica ou mesmo um prédio específico, em um mapa mais detalhado. Por exemplo, a Unicamp pode aparecer em um mapa de Campinas com um certo nível de detalhes, ou em um mapa de Barão Geraldo com mais detalhes.

Gugo comprou uma grande coleção de mapas retangulares e deseja criar um serviço para processar seqüências de consultas em mapas com vários níveis de detalhes. As localidades são representadas por um par de coordenadas inteiras (x, y). Os mapas têm identificadores únicos e são representados por dois pares de coordenadas, descrevendo cantos opostos do mapa. Os lados de todos os mapas são paralelos aos eixos cartesianos padrão x e y. Um mapa abrange todas as localidades contidas no retângulo, incluindo as que estão sobre a borda.

O nível de detalhe de um mapa pode ser estimado pelo tamanho da área retangular representada pelo mapa: um mapa que cobre uma área menor contém informações mais detalhadas e portanto maior nível de detalhe.

Pode haver sobreposição das áreas cobertas pelos mapas. Se uma consulta é feita para uma localidade presente em dois ou mais mapas, o mapa preferido é o de maior nível de detalhe. Em caso de empate, o preferido é o mapa em que a localidade é mais próxima do centro do mapa. Finalmente, se ainda houver empate, o mapa preferido é o de menor identificador.

Tarefa

Dados o conjunto de mapas e uma lista de consultas de localidades você deve escrever um programa que determine, se existir, o mapa com o maior nível de detalhe para cada uma das consultas.

Entrada

A entrada é composta de vários conjuntos de testes. A primeira linha de um conjunto de testes contém dois inteiros M, e R, separados por um espaço em branco, que indicam respectivamente o número de mapas (1 <= M <= 30000) e o número de consultas (1 <= R <= 50000). Cada uma das M linhas seguintes contém cinco inteiros I, X1, Y1, X2, Y2, separados por um espaço em branco; I representa o identificador do mapa (1 <= I <= M ), (X1, Y1) representa a coordenada do canto inferior esquerdo do mapa, e (X2, Y2) representa a coordenada do canto superior direito do mapa (−10000 <= X1 < X2 <= 10000 e −10000 <= Y1 < Y2 <= 10000). Muitos dos mapas (mesmo de áreas disjuntas) têm cantos com coordenadas x ou y coincidentes. O número máximo de cantos de mapas com coordenadas x não coincidentes é 500, e o número máximo de cantos de mapas com coordenadas y não coincidentes também é 500. As R linhas seguintes contêm as consultas. Cada consulta é dada em uma linha contendo dois inteiros XR e YR, representando uma localidade (−10000 <= XR <= 10000 e −10000 <= YR <= 10000). O final da entrada é indicado por M = R = 0.

Saída

Para cada conjunto de teste da entrada seu programa deve produzir a saída da seguinte forma. A primeira linha deve conter um identificador do conjunto de teste, no formato ‘Teste n’, onde ‘n’ é numerado seqüencialmente a partir de 1. Para cada consulta do conjunto de testes da entrada seu programa deve imprimir uma linha, contendo um inteiro N, representando o mapa preferido para a localidade, se existir. Se não existir mapa para a localidade desejada imprima o valor zero. A última linha deve ser deixada em branco. A grafia mostrada no Exemplo de Saída, abaixo, deve ser seguida rigorosamente.

Entrada:
2 4
1 1 1 4 5
2 3 2 7 8
4 2
5 3
6 9
2 2
4 4
4 1 -3 4 2
2 -3 -4 2 -1
3 -4 -2 -1 3
1 -2 1 3 4
0 0
2 -3
1 3
-2 1
0 0

Saída:
Teste 1
1
2
0
1

Teste 2
0
2
1
3

1 <= M <= 30000 (M = 0 para indicar final da entrada)
1 <= N <= 50000 (N = 0 para indicar o final da entrada)
-10000 <= X1 < X2 <= 10000
-10000 <= Y1 < Y2 <= 10000