풍선

프로그래밍 대회를 열 때 번거로운 일 하나는 손에서 놓쳐 천장까지 올라간 풍선을 걷어내는 것이다. 대회장 임대 계약에는 행사 직후 청소를 마쳐야 한다는 조항이 흔히 들어가고, 지키지 못하면 위약금을 낸다. 올해 주최 측은 미리 천장 설계도를 받아 두었다. 바닥의 어느 점에서 풍선을 놓았는지에 따라 그 풍선이 천장에 막혀 어디에 걸리는지, 아니면 대회장 밖으로 빠져나가는지 알고 싶어 한다.

천장을 옆에서 보면 선분 $N$개다. 두 선분은 어떤 점도 공유하지 않는다.

풍선은 점 하나로 본다. 바닥의 $(X, 0)$에서 놓으면 수직으로 올라가고, 그다음은 처음 닿는 선분에 따라 갈린다. 선분의 두 끝점도 그 선분에 속하므로, 끝점으로 정확히 올라간 풍선은 그 선분에 닿은 것이다.

• 닿은 선분이 수평이면 풍선은 그 자리에 걸린다.
• 닿은 선분이 기울어져 있으면 풍선은 선분을 따라 미끄러져 그 선분의 가장 높은 끝점까지 올라가고, 그 점에서 다시 수직으로 올라간다. 그다음 다른 선분에 닿을 수도 있고, 대회장 밖으로 빠져나갈 수도 있다.

아래 그림은 천장 하나를 보여 준다. 바닥에 표시한 네 점 a, b, c, d는 각각 $x = 2$, $x = 5$, $x = 6$, $x = 8$이다.

이 천장에서 a와 b에 놓은 풍선은 둘 다 $(2, 5)$에 걸리고, c에 놓은 풍선은 $(6, 5)$에 걸린다. d에 놓은 풍선은 천장에 막히지 않고 $x = 7$에서 대회장 밖으로 빠져나간다.

천장 정보를 읽고, 바닥에서 놓은 풍선이 최종적으로 어디에 있는지 묻는 질의 $C$개에 답하는 프로그램을 작성하시오.

첫째 줄에 천장을 이루는 선분의 개수 $N$과 질의의 개수 $C$가 주어진다.

다음 $N$개 줄에는 각각 정수 네 개 $X_1$, $Y_1$, $X_2$, $Y_2$가 주어진다. 두 끝점이 $(X_1, Y_1)$과 $(X_2, Y_2)$인 천장 선분이다.

다음 $C$개 줄에는 각각 정수 $X$ 하나가 주어진다. $(X, 0)$에서 놓은 풍선이 어떻게 되는지 묻는 질의다.

제한

• $1 \le N \le 10^5$
• $1 \le C \le 10^5$
• $0 \le X_1, X_2 \le 10^6$
• $0 < Y_1, Y_2 \le 10^6$
• $X_1 \ne X_2$
• 모든 선분을 함께 보았을 때, 끝점의 x좌표 $2N$개는 서로 다르다.
• 두 선분은 어떤 점도 공유하지 않는다.
• $0 \le X \le 10^6$

질의마다 한 줄씩, 입력에 주어진 순서대로 출력한다. 풍선이 대회장 밖으로 빠져나가면 빠져나가는 지점의 x좌표 하나를 출력한다. 그렇지 않으면 풍선이 천장에 걸린 위치 $(x, y)$를 정수 $X$와 $Y$ 두 개로, 공백 하나로 구분해 출력한다.