Hide

Problem C
Mad Diamond

Mars lacks a global magnetic field. Advanced gadgets can detect weak local magnetic fields and serve as compasses for navigation.

A compass of this kind depends of movement of a highly magnetized diamond crystal in an intricate maze inside the gadget. The crystal is often called Mad Diamond because of the apparent complexity of its movement.

A compass maze is built on a system of concentric rings located on a flat disk with a single so-called base point on its perimeter. On each ring, there are located $360$ so-called principal points in regular distances from each other. The angle of a principal point is the angle between two specific rays, measured in degrees. The first ray points from the maze center to the base point, the second ray points from the center of the maze to the principal point. The angle of the first principal point on a ring is $0^\circ $, the angle of the next principal point in the clockwise direction is $1^\circ $, and so on.

The maze itself consists of circular arc segments and straight radial segments. A circular arc segment is always completely embedded in one of the rings. It begins in a principal point and it ends also in a principal point. Each radial segment connects two neighbour rings and it is perpendicular to the tangents of the rings at the respective points of connection. Often, at least one endpoint of a radial segment belongs to a circular arc segment too, but that is not a strict necessity. Any two segments can intersect only at a principal point. No two segments overlap, not even partially.

Before calibration of a compass is started, two points in the maze are given, a principal start point and a principal end point. The diamond is located in the principal start point. The diamond has to travel from the principal start point, move along the segments in the maze, and finally stop at the principal end point.

During calibration, the compass is hanged vertically on a wall, with the base point initially at the top of the compass. Calibration proceeds in phases. In a phase, the compass remains fixed, and the diamond falls through the maze, from its previous position to the lowest currently reachable point in the maze. The phase is terminated when the diamond stops. The diamond may also remain still during a phase, if its position in the maze prevents it from movement. Between each two consecutive phases, the compass is rotated clockwise or counterclockwise by $1^\circ $.

Most of the time, due to the maze shape, the diamond cannot move exactly vertically. At any point of time, the vector of diamond movement can deviate from vertical vector by at most $89^\circ $. Note that at the end of each phase the diamond is in some principal point.

When the diamond arrives at a principal point from which two segments continue currently downwards, it always checks the radial segment. If the current vector of diamond movement through the radial segment would deviate from the vertical by at most $45^\circ $, the diamond falls into the segment and continues its movement down through it. Otherwise, the diamond continues its present movement through the circular segment.

Input

The first line contains a single number $N$ ($1 \le N \le 20$), the number of rings in the maze.

Then, $N$ pairs of lines follow. Each pair describes one ring, in the order from the center of the maze (the rings are numbered $0, 1, \dots , N - 1$). The first line in a pair starts with an integer $K$, the number of maze circular arc segments on the current ring. It is followed by $K$ pairs of integers ($X$ and $Y$) representing an arc starting in a principal point whose angle is X and ending in principal point whose angle is Y going clockwise.

The second line in the pair contains the integer $L$, the number of radial segments leading from the current circle out to the next ring. This number is followed by $L$ integers, the angles of principal points on which the radial segments are located.

The last two lines of input represent the principal start point and the principal end point, respectively. Each point is described by the number of ring it lies on and the angle of the principal point it coincides with.

Output

Print the minimum number of compass rotations between the phases which bring the diamond from the principal start point to the principal end point. The diamond must be standing still in the principal end point at the end of the last phase.

Print the string “Impossible” if the diamond cannot be brought to the principal end point at the end of any phase.

Sample explanation

\includegraphics[width=0.4\textwidth ]{fig}
Figure 1: An illustration of the path of the diamond in the first sample.
Sample Input 1 Sample Output 1
3
2 30 80 90 140
2 45 110
2 0 60 90 180
1 30
1 30 140
0
0 30
2 140
260
Sample Input 2 Sample Output 2
3
2 30 80 90 10
2 45 110
2 0 60 90 180
2 30 100
1 30 140
0
0 30
0 10
594

Please log in to submit a solution to this problem

Log in