Determine Flight Path Safety

You are given a set of restricted zones in the plane, each defined as a circle with center \( (x, y) \) and radius \( r \). You are also given two points: the start \( (x_s, y_s) \) and the end \( (x_e, y_e) \) of a flight path. The flight path is modeled as a line segment connecting the start and end points.

Your task is to determine whether the flight path intersects any of the restricted zones. An intersection is considered to occur if there exists a parameter \( t \) with \( 0 \le t \le 1 \) such that the point \[ P(t) = (x_s, y_s) + t \cdot (x_e - x_s, y_e - y_s) \] satisfies the circle equation \[ (x_s + t(x_e-x_s) - x)^2 + (y_s + t(y_e-y_s) - y)^2 = r^2. \] Use the quadratic formula to solve for \( t \) (note that the equation may have zero, one, or two solutions). If at least one solution lies in the interval \([0,1]\), the flight path is considered to be RESTRICTED. Otherwise, the flight path is SAFE.

Note: The input format uses stdin and the output must be printed to stdout.

inputFormat

The input is given from stdin and has the following format:

n
x1 y1 r1
x2 y2 r2
... (n lines for each restricted zone)
xs ys xe ye

Where:

• n is an integer representing the number of restricted zones.
• Each restricted zone is given by three integers \(x, y, r\) representing its center and radius.
• The last line contains four integers representing the start point \((x_s, y_s)\) and the end point \((x_e, y_e)\) of the flight path.

outputFormat

Output a single line to stdout which is either SAFE if the flight path does not intersect any restricted zone, or RESTRICTED if it intersects at least one.

2
15 15 5
25 25 5
0 0 10 10

SAFE