Stars

On a clear, moon-less 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 identified groups of stars, called constellations, and gave them names — mostly from Greek mythology — that are still in use today. Examples are "Ursa Minor", "Pisces", "Cancer", and many others.

Given a sketch of a constellation, it is not easy for an amateur to actually find it in the sky. Moreover, simple constellations — such as "Triangulum" (a triangle), which consists of only three stars — may appear several 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 collection of points in the plane, each with an associated brightness. You are also given several constellations, each a set of points in the plane. For every constellation you must determine:

• the number of times it occurs in the star map, and
• the greatest brightness of any occurrence, if at least one exists.

An occurrence is a subset of stars from the map that forms a copy of the constellation obtained by translation, rotation, and uniform (positive) scaling only — that is, a direct, orientation-preserving similarity. Reflections (mirror images) are not allowed. Two occurrences are considered the same if and only if they consist of exactly the same subset of map stars.

The total brightness of an occurrence is the sum of the brightnesses of the stars it consists of. Because every occurrence of a given constellation contains the same number of stars, the occurrence with the greatest total brightness is also the one with the greatest average brightness; we report that maximum total brightness.

The input contains the descriptions of several star maps. Each map starts with a line containing a single integer $n$, the number of stars in the map ($1 \le n < 1000$). Each of the following $n$ lines contains three integers: the $x$-coordinate, the $y$-coordinate, and the brightness of one star. The larger the value, the brighter the star.

The next line contains a single integer $m$, the number of constellations that follow ($1 \le m < 50$). Each constellation description starts with a line containing an integer $s_i$, the number of stars in constellation $i$, followed by a string $N_i$, the name of the constellation ($N_i$ has at most 40 characters and contains no blanks). The following $s_i$ lines each contain the $x$- and $y$-coordinates of one point of the constellation.

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

Because all star coordinates are integers, any rotated or scaled placement of a constellation whose points would not fall on integer coordinates can immediately be ruled out.

For each star map, first output the number of the map ("Map #1", "Map #2", and so on) on a line of its own.

For each constellation, in the same order as in the input, output a blank line, then a line stating its name and how many times it occurs in the map, in the form:

<name> occurs <k> time(s) in the map.

If the constellation occurs at least once, output on the next line the greatest total brightness of any of its occurrences, in the form:

Brightest occurrence total brightness: <B>

If it does not occur, output no brightness line for it.

After the last constellation of a star map, output a line consisting of exactly five dashes ("-----").