Reflections

Rendering realistic images of imaginary environments or objects is an interesting topic in computer graphics. One of the most popular methods for this purpose is ray tracing.

To render images using ray tracing, one traces the path that rays of light entering a scene take. In this problem you will write a program that computes such paths in a restricted environment.

For simplicity, we consider only two-dimensional scenes. Every object in the scene is a totally reflective (mirror) sphere. When a ray of light hits such a sphere, it is reflected so that the angle between the incoming ray and the tangent equals the angle between the leaving ray and the tangent.

Given a scene description and a ray entering the scene, your task is to determine which spheres the ray hits.

The input consists of a series of scene descriptions. Each description starts with a line containing the number $n$ ($n \le 25$) of spheres in the scene. Each of the following $n$ lines contains three integers $x_i$ $y_i$ $r_i$, where $(x_i, y_i)$ is the center and $r_i > 0$ is the radius of the $i$-th sphere. This is followed by a line containing four integers $x$ $y$ $dx$ $dy$ describing the ray: it originates from the point $(x, y)$ and initially points in the direction $(dx, dy)$. At least one of $dx$ and $dy$ is non-zero.

The spheres are disjoint and non-touching. The ray does not start inside a sphere and never touches a sphere tangentially.

A scene starting with $n = 0$ terminates the input and must not be processed.

For each scene, first output the scene number. Then print the numbers of the spheres that the ray hits within its first ten deflections (spheres are numbered according to their order in the input).

If the ray hits at most ten spheres and then heads towards infinity, print inf after the last sphere it hits. If the ray hits more than ten spheres, print three dots (...) after the tenth sphere.

Print a blank line between consecutive scenes.