Cell Towers

A mobile phone gets service by connecting to a nearby cell tower. At any moment several towers may be in range, but the phone connects only to the one with the strongest signal. Your task is to track a traveler carrying a phone: at each mile marker along a road, determine which tower the phone is using, and report every marker where that tower differs from the previous marker.

Each tower has a position given as integer X-Y coordinates (in miles, relative to an arbitrary origin) and a power. The traveler follows a road made of straight line segments joined end to end; the road never crosses itself. Mile markers are placed every mile along the road, with mile marker 0 at the starting point.

If the road ends at least 0.5 miles beyond the last mile marker, the endpoint is labeled with the next mile. For example, a road 8.6 miles long has its endpoint labeled mile 9, while a road 8.2 miles long ends at regular mile marker 8.

If a tower with power $p$ is at distance $d$ from a marker, its signal strength there is $p / d^2$, rounded to the nearest integer (an exact half is rounded up). No tower is ever placed exactly at a mile marker. At each marker the phone uses the tower with the greatest signal strength; if two or more towers tie, the phone uses the one whose label comes first in the alphabet.

Worked examples (matching the three sample data sets):

• First sample: towers A at (1, 4) and B at (5, 4), both with power 1000, on a road whose segments follow the grid. At markers 0 and 1, A is stronger. At markers 2-4 A and B tie, so the earlier letter A is reported. At markers 5-9 B is stronger. At mile 10 the two are tied again, so A is reported, and A stays strongest to the end.
• Second sample: three towers, A at (0, 0) and C at (6, 6) with power 1000, and B at (6, 0) with power 600. A is strongest first; C is strongest at markers 3-8. The road ends at (5, 2), more than half a mile past mile 8, so the endpoint is labeled mile 9; there B is strongest, differing from mile 8, so the endpoint is reported.
• Third sample: like the second, but the road starts elsewhere and tower B has power 300. A is strongest first, then C at markers 2-7. The endpoint at (5, 2) is less than 0.5 miles past mile marker 7, so it is not labeled, even though B would be strongest there.

The input contains one or more data sets, followed by a line containing a single 0.

The first line of a data set contains two space-separated integers $T$ and $R$:

• $T$ is the number of towers, $1 \le T \le 10$.
• $R$ is the number of straight segments making up the road, $1 \le R \le 10$.

Each of the next $T$ lines contains three space-separated integers: the X-coordinate, Y-coordinate, and power of one tower. The towers are labeled 'A', 'B', 'C', ... in the order given.

The next line contains $2(R + 1)$ integers, the coordinates of the $R + 1$ points that define the road. The road starts at the first point and passes in straight segments through each of the remaining points.

All coordinates are integers from 0 to 100, inclusive, and no two given points are equal. Each tower's power is an integer from 1 to 1,000,000, inclusive.

Print one line for each road (data set). The line lists ordered pairs separated by single spaces. In each pair the first element is a mile marker and the second is the letter of the tower with the strongest signal there. Print an entry for mile 0 and for every mile marker whose strongest tower differs from the previous marker's. Each ordered pair is written in parentheses with the two elements separated by a comma and no spaces inside, for example (5,B).