Ether Geometry

Euclid, who lived in Alexandria and firmly believed there was no Royal Road to Euclidean Geometry, gradually began to feel, after reading newspaper articles, watching TV programs, and listening to young students, that a discipline such as eGeometry or Geometry on the Internet might be possible. In an e-Geometry environment, he could discuss geometry problems in time with many friends, including Pythagoras, or upload new versions of his famous archive "Elements of Geometry (Stoicheia)" to his website. He immediately decided to join the Internet.

He started laying ether cable himself from the hub to the terminal in his uniquely shaped study. He designed the cable route to be as short as possible.

Figure 1 is a plan of his study. Integers in parentheses, such as (0 0), are the x and y coordinates of the nearest pillar, hub, or terminal. Adjacent pillars are joined by walls, drawn as solid lines. Suppose A is the position of the hub and B is the position of the terminal. Then the shortest cable may run along the broken line in the figure. Your task is to output the sequence of coordinates of the turning points of the shortest cable route, including both ends A and B, for each plan. For example, the answer for Figure 1 is (1 1) (2 2) (8 4) (9 5).

Figure 1

This is, however, the house of Euclid, the founder and master of Euclidean Geometry. The pillars, hub, and terminal are ideal points of Euclidean Geometry, and the walls and cable are line segments in the geometric sense. So the cable may overlap walls or pillars. For Figures 2, 3, and 4, the answers are as follows. From here on, each study layout is given as a list of pillar coordinates.

Figure 2. Pillars: (0 0) (2 0) (2 2) (4 2) (4 0) (6 0) (6 6) (4 6) (4 4) (2 4) (2 6) (0 6). Hub: (1 1). Terminal: (5 1). Answer: (1 1) (2 2) (4 2) (5 1).

Figure 3. Pillars: (0 0) (2 0) (2 2) (4 2) (4 0) (6 0) (6 6) (4 6) (4 4) (2 4) (2 6) (0 6). Hub: (1 1). Terminal: (5 5). Answer: (1 1) (5 5). Warning: (2 2) (4 4) are not turning points.

Figure 4. Pillars: (0 0) (2 0) (2 2) (4 2) (4 0) (6 0) (6 2) (8 2) (8 0) (10 0) (10 6) (8 6) (8 4) (6 4) (6 6) (4 6) (4 4) (2 4) (2 6) (0 6). Hub: (1 1). Terminal: (9 1). Answer: (1 1) (2 2) (8 2) (9 1).

Figure 2	Figure 3	Figure 4

Your program must solve layouts with complicated shapes such as Figure 5. This layout is included in the sample input.

Pillars: (0 0) (2 0) (2 4) (4 4) (4 0) (14 0) (14 6) (10 6) (10 8) (14 8) (14 14) (4 14) (4 10) (2 10) (2 14) (0 14) (0 8) (6 8) (6 12) (12 12) (12 10) (8 10) (8 4) (12 4) (12 2) (6 2) (6 6) (0 6). Hub: (1 1). Terminal: (1 13). Answer: (1 1) (2 4) (4 4) (6 2) (12 2) (12 4) (10 6) (10 8) (12 10) (12 12) (6 12) (4 10) (2 10) (1 13).

Figure 5

All coordinates are integers. Walls are parallel to the x-axis or the y-axis. At each pillar with given coordinates, a wall turns right or left. The pillar coordinates are listed in the order you see when you look inside the study with the inside on your left. The wall after the last pillar in the list runs to the first pillar. Each pillar appears only once in the list. Each pillar is connected to exactly two walls, one parallel to the x-axis and one parallel to the y-axis. The walls form one closed line around the study. No walls cross, and no walls branch. The study has no independent walls or other obstacles inside. Each data set has exactly one hub and one terminal inside the study, and their positions are always different.

The input contains one or more data sets. Each data set begins with an integer n (4 <= n <= 208), the number of pillars. The following lines contain the pillar coordinates, five pairs per line. The next line contains the hub coordinates (ax ay) and the terminal coordinates (bx by).

n
x1   y1   x2   y2   ...  x5   y5
x6   y6   x7   y7   ...  x10  y10
x11  y11  ...
     ...  xn   yn
ax   ay   bx   by

The input and output values do not use parentheses.

All pillar coordinates are even integers. The hub and terminal coordinates are odd integers. The room is less than 100 units in both the x and y directions, and the cable is shorter than 1000 units.

The input ends with a line containing a single 0 after the last data set.

For each data set, print the sequence of turning point coordinates of the shortest cable. The sequence starts with the hub and ends with the terminal. Print five coordinate pairs per line, separated by single spaces. The last line may contain fewer than five pairs. Separate x and y within each pair with a single space. The last coordinate on a line may be followed by a single space. Print one empty line after the answer for each data set.