Stars

On a clear, moonless night you can see millions of stars glimmering in the sky. Faced with this overwhelming number, the Greeks began — nearly 2,000 years ago — to bring some order to the chaos. They grouped stars into constellations and gave them names that are still in use today, such as "Ursa Minor", "Pisces", and "Cancer".

Given only a sketch of a constellation, an amateur cannot easily find it in the real sky. Worse, the shape of a simple constellation — for example "Triangulum", a triangle of just three stars — may appear many times, and singling out the correct occurrence is hard.

In this problem we let the computer find constellations in the sky.

You are given a star map: a set of points in the plane, each with an associated brightness. You are also given a constellation, again as a set of points in the plane. For the constellation you must report:

• how many times it occurs in the star map, and
• the position of its brightest occurrence, if any occurrence exists. (The idea: if a constellation seems to appear several times, the brightest one is most likely the real one, because it is the most eye-catching.)

An occurrence is a subset of the map's stars that forms an arbitrarily rotated and/or scaled copy of the constellation's stars (translation is also allowed; reflections are not). A given subset may fit the constellation in several orientations — a square fits in 4 ways under $90^\circ$ rotations — but such rotations of the same subset do not count as separate occurrences.

The brightness of an occurrence is the average brightness of its stars: the sum of the individual brightnesses divided by the number of stars in the constellation.

The input describes several star maps.

Each map begins with a line containing a single integer $N$ — the number of stars in the map ($1 \le N < 1000$). The next $N$ lines each contain three integers: the $X$- and $Y$-coordinates and the brightness of one star. A larger value means a brighter star.

The following line contains a single integer $M$ — the number of constellations to process ($1 \le M < 50$). Each constellation description begins with a line containing an integer $S$ (the number of stars in the constellation) and a string $C$ (its name; at most 40 characters, containing no blanks). The next $S$ lines each contain the $X$/$Y$-coordinates of one constellation star.

All coordinates lie in the range $-1000$ to $1000$; brightness values lie in the range $0$ to $100$.

A blank line separates one star map from the next. The input ends with an empty map ($N = 0$), which must not be processed.

Note: because all star coordinates are integers, you can immediately reject any rotated or scaled placement of the constellation whose points would not land on integer coordinates.

For each star map, first print the map number on its own line: Map #1 for the first map, Map #2 for the second, and so on.

Then, for each constellation — in the same order as the input — print one line of the form <name> occurs <k> time(s) in the map., where <name> is the constellation's name and <k> is the number of times it occurs.

If <k> is at least 1, print on the next line Brightest occurrence: followed by the positions of the stars of the brightest occurrence, each written as (x,y) and separated by single spaces. Print the positions in ascending order of $X$-coordinate; stars sharing the same $X$-coordinate are ordered by ascending $Y$-coordinate. You may assume that every constellation has a single, unique brightest occurrence in each map.

Print a blank line before each constellation, and a line of five dashes (-----) after each star map.