Spherical Regions on a Sphere

In this problem, a sphere of radius \(\boldsymbol{R}\) with center at the origin is considered. The north pole of the sphere is defined as the point \((0, 0, R)\). Two types of circles on the sphere are defined as follows:

• Safe circles: Tinytree selects \(N\) pairs of points on the sphere. For each pair, together with the north pole, a circle is uniquely determined. We guarantee that the spherical radius (i.e. the geodesic radius on the sphere) of each circle is strictly less than \(R\) so that the circle divides the sphere into two regions of unequal area. The interior of a circle is defined as the portion with the smaller area.
• Dangerous circles: Similarly, ustze selects \(M\) pairs of points on the sphere. Each pair together with the north pole determines a circle (with spherical radius strictly less than \(R\)). The interior (i.e. the smaller-area part) of each such circle forms the dangerous region.

The safe region is the union of the interiors of all safe circles, and the dangerous region is the union of the interiors of all dangerous circles.

Kiana has identified \(T\) points on the sphere. For each point, determine whether it lies in the safe region and/or in the dangerous region. For each query point, output two numbers separated by a space. The first number should be 1 if the point lies inside at least one safe circle and 0 otherwise; the second number should be 1 if the point lies inside at least one dangerous circle and 0 otherwise.

How to decide if a point is inside a given circle on the sphere?

Each circle is defined by three points: the north pole \(A=(0,0,R)\) and two other points \(B\) and \(C\) on the sphere. Let \(u = B - A\) and \(v = C - A\). Then the (nonzero) cross product \(n = u \times v\) is perpendicular to the plane containing the circle. We normalize \(n\) so that \(n\) is a unit vector and force \(n\) to satisfy \(n \cdot A > 0\) (if not, set \(n \leftarrow -n\)). Let \(d = n \cdot A\). Then for any point \(X\) on the sphere, since the spherical radius of the circle is \(\arccos(\frac{d}{R})\) (which is less than \(\frac{\pi}{2}\)), the point \(X\) is inside the circle if and only if \[ n \cdot X > d. \] This same check is used for both safe and dangerous circles.

Input / Output details:

inputFormat

The input consists of the following:

1. The first line contains four numbers: \(R\) (a real number), \(N\) (an integer), \(M\) (an integer) and \(T\) (an integer), where \(R\) is the radius of the sphere.
2. The next \(N\) lines each contain 6 real numbers: the coordinates of two points \(B\) and \(C\) (i.e. Bx By Bz Cx Cy Cz) that, together with the north pole \(A = (0,0,R)\), define a safe circle.
3. The following \(M\) lines each contain 6 real numbers defining a dangerous circle in the same format as above.
4. The last \(T\) lines each contain 3 real numbers representing a query point \(X\) (i.e. Xx Xy Xz) on the sphere.

You may assume that all given points lie on the sphere (i.e. satisfy \(x^2 + y^2 + z^2 = R^2\)) and that for each circle the spherical radius is strictly less than \(90^\circ\) (which implies \(n \cdot A = d > 0\)).

outputFormat

For each of the \(T\) query points, output a line with two integers separated by a space. The first integer is 1 if the point lies in the safe region (i.e. inside at least one safe circle) or 0 otherwise; the second integer is 1 if the point lies in the dangerous region (i.e. inside at least one dangerous circle) or 0 otherwise.

sample

5 1 1 3
5 0 0 0 5 0
-5 0 0 0 -5 0
0 0 5
3 0 4
-3 0 4

0 0
1 0
0 1