ustze likes geometry and believes it is the simplest part of mathematics competitions. After conquering mathematics, ustze decided to bring his talent to computational geometry and compete against traditional Euclidean geometry.

As a defender of Euclidean geometry, Tinytree established a sphere in three-dimensional space centered at the origin with radius $R$. The point with coordinates $(0, 0, R)$ is called the North Pole, which clearly lies on the sphere. Tinytree recalls that in Euclidean geometry, three points uniquely determine a circle in space. Therefore, Tinytree determined $N$ pairs of points on the sphere. Each pair, together with the North Pole, determines a circle on the sphere. We guarantee that the radii of these circles are strictly less than $R$. Thus, each circle divides the sphere into two parts of unequal area. We call the part with the smaller area the interior of the circle, and the part with the larger area the exterior. The union of the interiors of these $N$ circles forms the safe region.

As a fanatic of non-Euclidean geometry, ustze believes that circles on the sphere are actually "straight lines." He determined $M$ pairs of points on the sphere. Each pair, together with the North Pole, also determines a circle on the sphere. The radii of these $M$ circles are also strictly less than $R$. The union of the interiors of these $M$ circles forms the danger region.

Just as Tinytree and ustze were confronting each other, Kiana happened to pass by on the sphere. Seeing this scene, she was terrified and began to hide on the sphere. Now, Kiana has preliminarily identified $T$ points on the sphere and wants to know whether these points are in the safe region or the danger region so that she can escape. Since Kiana cannot calculate this herself, she hopes you can help her.

Input

Read from standard input.

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 determined by Tinytree, the number of point pairs determined by ustze, and the number of escape points determined by Kiana, respectively.

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

The next $N$ lines each contain $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$), where $A_i, B_i$ represent the $x$ and $y$ coordinates of the first point in the $i$-th pair determined by Tinytree. $X_i$ is '+' if the $z$-coordinate of the first point is greater than 0, and '-' if it is less than 0. If the $z$-coordinate is 0, $X_i$ is chosen randomly from '+' and '-'. $C_i, D_i$ represent the $x$ and $y$ coordinates of the second point in the $i$-th pair, and $Y_i$ represents the sign of the $z$-coordinate, with the same meaning as $X_i$.

The next $M$ lines each contain $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 the $j$-th pair determined by ustze, with the same representation as before.

The next $T$ lines each contain 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 the $k$-th escape point determined by Kiana, with the same representation as before.

The data is guaranteed to be valid, no two points in the input are identical, all real numbers are given to three decimal places, and the minimum straight-line distance between Kiana's escape points and any given circle is not less than $10^{-6}$.

Output

Output to standard output.

Output $T$ lines in total, each containing 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 but also not in the danger region, output "Passer" on the $k$-th line. If it is not in the safe region but is in the danger region, output "Goodbye" on the $k$-th line (all outputs without quotes).

Examples

Input 1

1 2 2
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 +

Output 1

Passer
Safe
Goodbye
Safe

Note

In three-dimensional space, we can use an ordered triple of real numbers $(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, respectively.

A sphere in three-dimensional space with center $(x_0, y_0, z_0)$ and radius $R$ is 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 distinct points $(x_1, y_1, z_1)$ and $(x_2, y_2, z_2)$ on the sphere, if they are not antipodal points (two points are antipodal if and only if the distance between them is $2R$), they are not collinear with the center of the sphere. These three points uniquely determine a plane. The intersection of this plane and the sphere is a circle, which is divided into two parts by these two points. The length of the shorter part is called the distance between these two points on the sphere. If the two points are antipodal, the distance between them is defined as $\pi R$. A circle on the sphere is the set of points on the sphere whose spherical distance to a certain point on the sphere is equal to a constant. It can be proven that any three distinct points on the sphere uniquely determine a circle on the sphere.