청소 로봇

도시의 도로망은 축에 평행한 사각형들의 집합으로 이루어진다. 사각형끼리는 아래 그림처럼 겹칠 수 있다. 이 도시는 매일 도로망 전체를 청소하는 자율 청소 로봇을 운영한다. 청소하는 동안 각 사각형은 다음 세 가지 중 하나로 분류된다. 미청소(UC) 사각형은 로봇이 한 번도 방문하지 않은 사각형이다. 부분 청소(PC) 사각형은 일부만 청소된 사각형이다. 전체 청소(AC) 사각형은 완전히 청소된 사각형이다.

로봇은 다음 경로 알고리즘을 따른다. 로봇은 각 사각형을 청소하면서 시계 방향으로 움직인다. 사각형을 청소하는 도중 새로운 UC 사각형의 도로를 만나면, 교차점에서 방향을 틀어 그 UC 사각형 쪽으로 이동한다. 사각형 청소를 마쳐 로봇이 점 $(x, y)$에 도달했을 때 같은 점 $(x, y)$에서 다른 PC 사각형을 만나면, 로봇은 그 점에서 PC 사각형의 청소를 이어서 한다. 로봇이 시작점으로 돌아오면 그 뒤로는 그 점에 머문다. 단위 거리를 이동하는 데 1초가 걸리고, 교차점이나 모서리에서 방향을 바꾸는 데 2초가 걸린다.

아래 예시로 알고리즘을 설명한다. 이 도로망은 사각형 $R_1$부터 $R_4$까지 네 개로 이루어져 있으며, 시작점은 $R_1$의 점 $s$이다.

아래 그림의 주황색 선은 $R_1$의 $s$에서 출발한 로봇의 이동 경로이다.

$n$개의 사각형 정보가 주어질 때, 다섯 질의 시각 $t_i$($1 \le i \le 5$)에서 로봇의 정확한 위치를 구하라. 시작점은 $R_1$의 왼쪽 위 모서리이다.

첫 줄에 사각형의 개수 $n$($1 \le n \le 50$)이 주어진다. 둘째 줄에는 다섯 질의 시각 $t_1$부터 $t_5$까지가 주어지며, $1 \le t_i \le 100000$이다. 이어지는 $n$개 줄의 $i$번째 줄에는 사각형 $R_i$의 정수 네 개 $x_l$, $y_l$, $x_u$, $y_u$가 주어진다. $(x_l, y_l)$은 왼쪽 아래 모서리, $(x_u, y_u)$는 오른쪽 위 모서리이며, $1 \le x_l < x_u \le 1000$, $1 \le y_l < y_u \le 1000$이다. 사각형끼리의 교점은 모두 변의 중간에 있고 모서리 위에 있지 않으며, 변이 겹치지도 않는다. 따라서 아래 그림과 같은 배치는 주어지지 않는다. 사각형들이 모두 하나의 연결 성분을 이루지는 않는다.

정확히 다섯 줄을 출력한다. $i$번째 줄에는 시각 $t_i$에서의 로봇 위치를 나타내는 정수 두 개 $x_i$와 $y_i$를 출력한다. 시각 $0$에서 로봇은 시작점에서 출발할 준비가 되어 있다.