| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 79 | 21 | 14 | 22.581% |
The road network of a city consists of a set of axis-parallel rectangles. Each rectangle road may overlap with others as shown in the figure below. The city operates an autonomous cleaning robot that is responsible to clean the entire roads every day. During cleaning, each rectangle is classified into one of three types as follows.
The cleaning robot works according to the following routing algorithm.
Let us explain the routing algorithm with the following example. The example road network consists of four rectangles $\{R_1, R_2, R_3, R_4\}$ where the starting point is $s$ of $R_1$.
The orange lines in the following figure depict the trajectory of the cleaning robot starting from $s$ of $R_1$.
Given information about $n$ rectangles, we want to know the exact locations of the robot for the five query points $t_i$ (1ドル ≤ i ≤ 5$) in time. Note that the starting point is designated to the upper left corner of the rectangle $R_1$.
Your program is to read from standard input. The input starts 1ドル ≤ i ≤ 5$ with a line containing one integer, $n$ (1ドル ≤ n ≤ 50$), where $n$ is the number of rectangles $R_i$. The second line gives the five query points $t_i$ (1ドル ≤ i ≤5$) in time where 1ドル ≤ t_i ≤ 100,000円$. The $i$-th line of following $n$ lines gives four integers $x_l,ドル $y_l,ドル $x_u,ドル $y_u$ for $R_i$ where $(x_l , y_l)$ is the lower left corner and $(x_u, y_u)$ is the upper right corner where 1ドル ≤ x_l < x_u ≤1,000円,ドル and 1ドル ≤ y_l < y_u ≤ 1,000円$. Note that the intersection points between rectangles are all in the middle of edges, not at corner points, and there are no edge overlaps among rectangles, so the configurations below are not given in this problem. Also note that rectangles are not necessarily all connected into one component.
Your program is to write to standard output. Print exactly five lines. The line should contain two integers $x_i,ドル $y_i$ where $(x_i, y_i)$ is the location of the cleaning robot at time $t_i$ (1ドル ≤ i ≤ 5$).
The following shows sample input and output for three test cases. Note that at time $t = 0,ドル the robot is ready to start at the starting point.
4 1234 10000 700 3000 5000 100 500 300 800 100 100 900 400 150 30 190 550 230 350 700 700
900 376 100 800 696 700 190 452 230 476
7 9001 8002 7003 6004 5005 200 100 300 800 350 100 500 800 600 100 700 800 100 600 800 700 100 400 800 500 100 200 800 300 900 200 1000 700
263 100 154 600 551 700 500 142 235 400
5 1298 5574 3332 1794 7141 400 150 650 700 100 100 750 500 200 400 850 600 500 300 1000 650 150 150 350 350
750 262 500 540 812 600 418 100 400 699