Balão

1305
Tempo Limite: 8 | Nível: 7

Descrição

Uma das principais dificuldades de organizar uma Maratona de Programação é recolher os bal˜oes que escapam e ficam presos no teto do salão: muitas vezes o contrato com o dono do salão exige que este seja entregue limpo logo após o evento, sob pena de multa.

Este ano a organização da Maratona está mais previdente: ela tem o desenho do teto do salão, e quer sua ajuda para determinar o que pode acontecer com um balão, dependendo da posição no solo onde ele é solto (isto é, se é bloqueado pelo teto ou se escapa para o exterior do salão).

O teto do salão é formado por vários planos que, vistos de lado, podem ser descritos por segmentos de reta, como mostrado na figura abaixo:

O balão pode ser considerado pontual. Quando um balão toca um segmento do teto que é horizontal, ele fica preso. Quando um balão toca um segmento que é inclinado, o balão desliza até o ponto mais alto do segmento e escapa, podendo escapar completamente do salão ou podendo tocar em mais segmentos. Não há pontos em comum entre os segmentos que formam o teto.

Por exemplo, se o balão for solto nas posições marcadas como a ou b, será bloqueado na posição de coordenadas (2, 5); se o balão for solto na posição marcada como c, será bloqueado na posição de coordenadas (6, 5); e se o balão for solto na posição marcada como d, não será bloqueado e escapará para fora do salão na posição de coordenada x = 7.

Escreva um programa que, dada a descrição do teto do salão como segmentos de reta, responde a uma série de consultas sobre a posição final de bal˜oes soltos do piso do salão.


Entrada

A primeira linha da entrada contém dois inteiros N e C indicando, respectivamente, o número de segmentos de reta do teto e o número de consultas. Cada uma das N linhas seguintes contém quatro inteiros X 1 , Y 1 , X 2 , Y 2 , descrevendo um segmento de reta do perfil do teto, com extremos de coordenadas (X 1 , Y 1 ) e (X 2 , Y 2 ).
Cada uma das C linhas seguintes descreve uma consulta e contém um inteiro X, indicando que a consulta quer determinar o que acontece com um balão solto no ponto de coordenada (X, 0).


Saída

Para cada consulta da entrada, seu programa deve imprimir uma única linha. Se o balão escapar do salão, a linha deve conter um único inteiro X, indicando a coordenada x pela qual o balão escapa do salão. Caso contrário, a linha deve conter dois inteiros X e Y indicando a posição (x, y) em que o balão fica retido no teto.

Restrições
• 1 ≤ N ≤ 105
• 1 ≤ C ≤ 105
• 0 ≤ X1 , X2 ≤ 106 , 0 < Y1 , Y2 ≤ 106 , X1 != X2
• não há dois valores de coordenadas x iguais, considerando todos os segmentos.
• 0 ≤ X ≤ 106


Exemplos de Entrada Exemplos de Saída

4 3
1 3 4 2
10 3 7 4
2 3 8 3
3 5 5 4
4
9
8

1
7
8 3

4 4
0 1 3 3
1 5 6 5
5 3 2 4
7 4 10 2
2
5
8
6

2 5
2 5
7
6 5

Efetue Login ou Cadastre-se para submeter uma solução.



Adaptado por Erich Rodrigues | Competição: Maratona de Programação da SBC 2013