Description

ustze likes geometry. He believes geometry is the easiest part of math contests. After conquering mathematics, ustze decided to bring his talent into computational geometry and compete with traditional Euclidean geometry.

As a defender of Euclidean geometry, Tinytree builds in 3D space a sphere with center at the origin and radius $\boldsymbol R$. The point with coordinates $(0,0,R)$ is called the North Pole, and obviously it lies on the sphere. Tinytree recalls that in Euclidean geometry, three points can uniquely determine a circle in space. Therefore, Tinytree chooses $N$ pairs of points on the sphere. For each pair, together with the North Pole, they determine a circle on the sphere. We guarantee that the radius of each such circle is strictly less than $\boldsymbol R$. Hence each circle divides the sphere into two parts of unequal area. We call the part with smaller area the interior of the circle, and the part with larger area the exterior of the circle. The interiors of these $N$ circles are protected by Tinytree, and their union forms the safe region.

As a fanatic of non-Euclidean geometry, ustze thinks that circles on a sphere are actually “straight lines”. He chooses $M$ pairs of points on the sphere. For each pair, together with the North Pole, they also determine a circle on the sphere. The radii of these circles are also strictly less than $\boldsymbol R$. The interiors of these $M$ circles are under ustze’s intimidation, and their union forms the dangerous region.

While Tinytree and ustze are confronting each other, a passerby named Kiana happens to be on the sphere. She is frightened by what she sees and starts to hide and move around on the sphere. Now Kiana has preliminarily chosen $T$ points on the sphere. She wants to know whether these points are in the safe region or the dangerous region so that she can decide where to run. Since Kiana cannot compute it herself, she hopes you can help her.

Input Format

The first line contains three positive integers $N, M$ and $T$ ($1 \le N, M \le 5000$, $1 \le T \le 1.5 \times {10}^5$), representing the number of point pairs chosen by Tinytree, the number of point pairs chosen by ustze, and the number of escape points chosen by Kiana.

The second line contains a positive integer $R$ ($1 \le R \le {10}^3$), representing the radius of the sphere.

The next $N$ lines: the $i$-th line contains $A_i, B_i, X_i, C_i, D_i, Y_i$ ($1 \le |A_i|, |B_i|, |C_i|, |D_i| \le R$, $1 \le A_i^2 + B_i^2, C_i^2 + D_i^2 \le R^2$). Here, $A_i, B_i$ are the $x$- and $y$-coordinates of the first point in Tinytree’s $i$-th pair, and $X_i$ is + meaning the $z$-coordinate of the first point is greater than $0$, and - meaning the $z$-coordinate is less than $0$. If the $z$-coordinate equals $0$, then $X_i$ is chosen randomly between + and -. Similarly, $C_i, D_i$ are the $x$- and $y$-coordinates of the second point in the pair, and $Y_i$ indicates the sign of its $z$-coordinate, with the same meaning as $X_i$.

The next $M$ lines: the $j$-th line contains $A_j, B_j, X_j, C_j, D_j, Y_j$ ($1 \le |A_j|, |B_j|, |C_j|, |D_j| \le R$, $1 \le A_j^2 + B_j^2, C_j^2 + D_j^2 \le R^2$), representing the coordinates of ustze’s $j$-th point pair. The representation of points is the same as above.

The next $T$ lines: the $k$-th line contains two real numbers $A_k, B_k$ ($1 \le |A_k|, |B_k| \le R$, $1 \le A_k^2 + B_k^2 \le R^2$) and a character $X_k$, representing Kiana’s $k$-th escape point. The representation of points is the same as above.

The testdata guarantees validity, and there are no two identical points in the input. All real numbers are given to three digits after the decimal point. The minimum straight-line distance between any of Kiana’s escape points and the circumference of any given circle is at least $\boldsymbol{{10}^{-6}}$.

Output Format

Output $T$ lines. Each line contains a string. If Kiana’s $k$-th escape point is in the safe region, output Safe on the $k$-th line. If it is not in the safe region and also not in the dangerous region, output Passer on the $k$-th line. If it is not in the safe region but is in the dangerous region, output Goodbye (all outputs are without quotes).

2 2 4
3
2.571 0.514 + 2.571 -0.514 +
-2.571 0.514 + -2.571 -0.514 +
0.514 2.571 + -0.514 2.571 +
0.514 -2.571 + -0.514 -2.571 +
2.118 -2.118 -
1.051 1.051 +
-0.468 1.870 +
-1.870 -0.468 +

Passer
Safe
Goodbye
Safe

Hint

In 3D space, we can use an ordered real triple $(x, y, z)$ to describe the position of a point, where $x, y, z$ are called the $x$-coordinate, $y$-coordinate, and $z$-coordinate of the point.

A sphere in 3D space with center at $(x_0, y_0, z_0)$ and radius $R$ refers to the set of all points $(x, y, z)$ satisfying $(x - x_0)^2 + (y - y_0)^2 + (z - z_0)^2 = R^2$. For two different points $(x_1, y_1, z_1), (x_2, y_2, z_2)$ on this sphere, if they are not a pair of antipodal points (two points are antipodal if and only if the distance between them is $2 R$), then these two points and the center are not on the same line. These three points uniquely determine a plane. The intersection of this plane with the sphere is divided by the two points into two parts, and the length of the shorter part is called the distance between the two points on the sphere. If the two points are antipodal, then their distance is defined as $\pi R$. A circle on a sphere refers to the set of points on the sphere whose spherical distance to some point on the sphere equals a constant. It can be proven that any three different points on the sphere uniquely determine a circle on the sphere.

[Source]

From the preliminary round of the 2021 Tsinghua University Programming Contest and Collegiate Invitational (THUPC2021).

Resources such as editorials can be found at https://github.com/THUSAAC/THUPC2021-pre.

Translated by ChatGPT 5