BSP Trees

When rendering a scene with several objects onto a screen, the order in which the objects are drawn matters. In general, an object farther from the screen should be drawn earlier, so that nearer objects drawn later appear on top of it. If two objects do not overlap, their relative drawing order does not matter.

A binary space-partitioning (BSP) tree is a data structure that helps determine such an ordering. Assume the screen lies in the xy-plane centered on the $z$-axis, and that the $z$-axis points away from the viewer. The viewer is located near $-\infty$ on the $z$-axis, and every object lies on the far side of the screen ($z > 0$).

The BSP tree is built by inserting a series of planes parallel to the $y$-axis. The first plane splits space into two regions: one containing the viewer and one not containing the viewer. Every object is assigned to the region it lies in, and all objects in the viewer's region must be drawn after all objects in the other region. At this point the BSP tree is a root with two children, one per region.

A second plane subdivides space again, splitting each of the two regions into two for four regions in total; the tree now has three levels, with the regions at the leaves (a region may hold several objects or none). This continues until every region holds at most one object, or until a fixed number of planes has been used. Once a region contains a single object it is not split further, even as more planes are added.

Because all objects are parallel to the $z$-axis, we only work with their projection onto the xz-plane (looking down the $y$-axis). The figure below shows the effect of using 1, 2, and 3 planes.

A simple traversal of the finished BSP tree then yields a correct rendering order for the objects.

The input describes a single scene.

• The first line contains an integer $n$ ($1 \le n \le 20$), the number of objects.
• Each of the next $n$ lines describes one object in the format m x1 z1 x2 z2 ... xm zm, where $m$ ($3 \le m \le 6$) is the number of vertices and each $(x_i, z_i)$ is a vertex of the object's cross-section in the xz-plane. Objects are labeled A, B, C, ... in the order they appear.
• The next line contains an integer $p$ ($1 \le p \le 10$), the number of planes.
• Each of the next $p$ lines contains x1 z1 x2 z2, two points on the line where that plane meets the xz-plane.

No plane's line intersects any object (not even an edge or vertex), and no plane is parallel to the $z$-axis. All coordinates are integers.

Print a single line: the object names in the order they should be rendered for the given BSP tree. If a region contains two or more objects, list those objects in alphabetical order.