Escape from the Park

In the capital of Byteland there is a fenced park whose area is a rectangle. Within the park, trees and visitors are represented as circles. There are four entrances, one at each corner of the park:

• 1: Bottom‐left
• 2: Bottom‐right
• 3: Top‐right
• 4: Top‐left

A visitor enters the park through one of these entrances. When entering or exiting, the visitor's circular body exactly touches both fence sides at that corner. Thus, if a visitor has radius \(r_v\), its center will be at:

• Entrance 1: \((r_v, r_v)\)
• Entrance 2: \((W - r_v, r_v)\)
• Entrance 3: \((W - r_v, H - r_v)\)
• Entrance 4: \((r_v, H - r_v)\)

The park also contains several trees. Each tree is given as a circle with center coordinates \((x, y)\) and radius \(r_t\). To avoid collision, visitors must always remain in the safe region defined as the rectangular area \([r_v,\; W - r_v] \times [r_v,\; H - r_v]\) and must not intersect any tree. In effect, a visitor with radius \(r_v\) must avoid the forbidden region around each tree, which is also a circle with the same center \((x,y)\) and an effective radius of \(r_t + r_v\). Two circles are considered in contact if they are tangent; overlapping is forbidden.

Your task is: for each visitor (each with a given entrance and radius \(r_v\)), determine through which entrances they can exit the park. A visitor may exit through an entrance if there exists a collision‐free continuous path from the entry point (at the corresponding corner) to the exit point (also at a corner) while remaining inside the safe region.

Observation: It turns out that obstacles (trees) may block movement between different parts of the park. In particular, if the tree obstacles (after inflating each tree by \(r_v\)) form a chain connecting the left and right boundaries of the safe region, then horizontal crossing is impossible (i.e. a visitor starting on the left cannot reach an exit on the right, and vice‐versa). Similarly, if a chain connects the top and bottom boundaries, then vertical crossing is impossible.

Thus, the exit possibilities can be determined as follows. Let the starting entrance be given. Define its horizontal side as left if the entrance is 1 or 4, and right if it is 2 or 3; similarly, define its vertical side as bottom if it is 1 or 2, and top if it is 3 or 4.

Then:

• If both horizontal and vertical crossings are blocked then the visitor can only leave by the same entrance through which they entered.
• If only horizontal crossing is blocked then the visitor can exit only through entrances on the same horizontal side as the start: entrances 1 and 4 for the left side, and entrances 2 and 3 for the right side.
• If only vertical crossing is blocked then the visitor can exit only through entrances on the same vertical side as the start: entrances 1 and 2 for the bottom, and entrances 3 and 4 for the top.
• If neither blocking structure is present then all four exits are reachable.

You are given the dimensions of the park and the list of trees, followed by the list of visitors (each specified by an entrance number and radius). Determine, for each visitor, the set of entrance numbers through which they can exit the park.

Input Format:

inputFormat

The input begins with a line containing two integers \(W\) and \(H\), representing the width and height of the park.

The next line contains an integer \(N\) denoting the number of trees. Each of the following \(N\) lines contains three numbers: \(x\), \(y\) and \(r_t\) (the center coordinates and radius of a tree).

The next line contains an integer \(M\) representing the number of visitors. Then, \(M\) lines follow; each contains two numbers: an integer (the entrance number, from 1 to 4) and a number \(r_v\) (the radius of the visitor).

outputFormat

For each visitor, output a line with the list of entrance numbers (in ascending order) through which the visitor can exit the park. The numbers should be separated by a single space.

sample

10 10
1
5 5 1
2
1 1
2 1

1 2 3 4
1 2 3 4

</p>