Grid
----

A `grid' (in the sense described here) is a geometric
data base that stores a set of `points' in a fashion
that makes it easy to look up which points are near
a query point.  It is possible to represent geometric
objects as points and use a grid to look up which
objects are near a query point.

The grids we are concerned with are binary trees
in which each node is associated with a rectilinear
region in (cx, cy, cz, r) 4-dimensional space.  Here
(cx, cy, cz) is the center of a 3-dimensional sphere
of radius r, so the 4-dimensional point represents
a 3-sphere.

Each child is associated with a subregion of its par-
ent's region, so that the regions of the two children
of a node are disjoint and their union is the parent
region.  The child regions are made by intersecting
the parent region with the halfspaces d <= v and d > v,
for some real number v and coordinate d.  Here d may
be cx, cy, cz, or r.

Leaves of the grid contain sets of 4-dimensional points.
In this problem we shall not be concerned with these
sets.

You are given a grid and a set of queries.  Each query
consists of a point p and a distance R, and the answer
is the subtree of nodes whose regions contain a 4D
point (cx,cy,cz,r) representing a sphere that is at
most distance R from p, i.e., ||p-(cx,cy,cz)|| <= r+R.

If you think about it you will find that the nodes of
the desired subtree are those whose 4D regions intersect
a 4D cone whose axis is parallel to the r-direction and
whose r = C slice is a 3-sphere of radius R+C and center
p.


Input 
-----

For each of several test cases, a line containing
just the test case name, followed a line containing

    cxmin cxmax cymin cymax czmin czmax rmin rmax

followed by lines containing a representation of the
grid, followed by one or more query lines, followed
by a line containing just a `*'.

The region of the grid root is
 
	cxmin < cx <= cxmax
	cymin < cy <= cymax
	czmin < cz <= czmax
	 rmin <  r <=  rmax

The grid representation has the syntax:

    <grid> ::= # | d/v(<grid>,<grid>)
    d ::= cx | cy | cz | r
    v ::= a real number

Here <grid> represents a tree node, # represents a leaf,
the first <grid> in d/v(<grid>,<grid>) represents the
left child, and the second <grid> represents the right
child.  The left child region is made by intersecting
the parent region with the halfspace d <= v, and the
right child region is made by intersecting with d > v.
Whitespace, including line feeds, is allowed only after
`(' and `,'.

A query is represented by a single line containing

	px py pz R

where (px, py, pz) is the query point and R the query
distance.

No grid will have more than 127 nodes.  There will be
no more than 1000 queries among all the test cases
taken together.  For each test case and query:

	cxmin < cxmax
	cymin < cymax
	czmin < czmax
	0 <= rmin < rmax
	0 <= R

All input numbers are in the range [-1000, +1000] and
have at most 3 decimal places.

Input ends with an end of file.


Output
------

For each test case, first a line containing an exact
copy of the test case name line, and then for each query
p, R, exactly one line (possibly very long) containing
a representation of the subtree of grid nodes whose
regions contain points that represent spheres within
distance R of point p.  This subtree is represented by
the syntax:

    <subtree> ::= # | * | (<subtree>,<subtree>)
    
and is a pruned version of the grid made by omitting
the `d/v's and representing omitted children by `*'.
Also there may not be ANY whitespace within the query
output line.

The input will be such that the output is unambiguous.


Sample Input
------ -----

-- SAMPLE 1 --
-10 10 -10 10 -10 10 0 2
cx/0(cx/-5(#,#),cx/5(#,#))
-10 0 0 0
-5 0 0 0
-2.5 0 0 0
-1 0 0 0
+1 0 0 0
+2.5 0 0 0
+5 0 0 0
+10 0 0 0
*
-- SAMPLE 2 --
-10 10 -10 10 -10 10 0 2
cx/5(cy/5(cz/5(r/1(#,#),
               r/1(#,#)),
          cz/5(r/1(#,#),
               r/1(#,#))),
     cy/5(cz/5(r/1(#,#),
               r/1(#,#)),
          cz/5(r/1(#,#),
               r/1(#,#))))
-13 -5 5 0.1
-12 -5 5 0.1
1 -5 5 0.1
1 -5 3 0.1
1 1 1 3.1
1 1 1 2.1
*


Sample Output
------ ------

-- SAMPLE 1 --
((#,*),*)
((#,#),*)
((*,#),*)
((*,#),(#,*))
((*,#),(#,*))
(*,(#,*))
(*,(#,#))
(*,(*,#))
-- SAMPLE 2 --
*
((((*,#),(*,#)),*),*)
((((#,#),(#,#)),*),*)
((((#,#),(*,#)),*),*)
((((#,#),(#,#)),((#,#),*)),(((#,#),*),*))
((((#,#),(*,#)),((*,#),*)),(((*,#),*),*))

Remarks
-------

In real applications, the spheres bound more complex
objects which are inspected further once it is determin-
ed that their bounding spheres are close enough to the
observation point.  Also, p and part of R may themselves
represent a sphere bounding a complex object.

Lastly, in a real application, the algorithm to select
grid nodes in the subtree may be simplified to be faster
at the cost of including some nodes that do not belong.
But you must NOT simplify for this problem, which
requires precise computation of intersections.


Reference
---------

Algorithms & Data Structures, with applications to
graphics and geometry, Jurg Nievergelt and Klaus H.
Hinrichs, 23.5.


File:	   grid.txt
Author:	   Bob Walton <walton@seas.harvard.edu>
Date:	   Sun Oct  5 05:53:46 EDT 2014

The authors have placed this file in the public domain;
they make no warranty and accept no liability for this
file.

RCS Info (may not be true date or author):

    $Author: walton $
    $Date: 2014/10/05 09:56:22 $
    $RCSfile: grid.txt,v $
    $Revision: 1.9 $