#P2087. Petanque

Petanque

Description

Petanque, a game which uses balls (some boules and one coche), was developed in the small town of La Ciotat, near Marseilles, France. The aim of the game is simple. If playing football is kicking a ball into the opposite goal and keeping it out of your own, playing petanque is placing your boules nearer to the coche and keeping your opponent's boules away.

One simplified version of the game is played between two players, one against the other, with three boules each. The players are located in a plane and one of them starts the game by throwing the coche forward. The player who throws the coche also throws the first boule. The opposing player throws the second boule. From then on, the player who has not thrown the boule which is the nearest to the coche throws the next boule (you may assume that there will be only one boule nearest to the coche). This continues until one player has thrown all his boules. After this, the other player throws all his remaining boules. The winner is the player who has thrown the ball which in the end is nearest to the coche (again, you may assume that there will be only one boule nearest to the coche). The winning player claims as many points as there are boules thrown by him nearer the coche than any other opposing boules.

You are invited to simulate some games of Petanque. For simulation purposes, we will consider that the playing floor is a plane and the balls are adimensional (they can be considered as points). You will be given the names of the two players. The first player given will be the first to play. For each ball (coche or boules) thrown, you will be given the starting position of the ball, its direction and how many meters it will roll. You may assume that the starting position of the balls are inside the playing floor, the balls will never leave the floor and the starting position of a ball will never coincide with the current position of another ball in the playing floor. The direction of each ball is given in degrees where the east direction (x-positive) corresponds to zero degrees and the degrees increase in the counter-clockwise direction, as shown in the figure below. When a ball that was thrown knocks another ball in its way, the

thrown ball stops. The ball which was still starts moving in the same direction for an amount of meters equal to the quantity of meters that the thrown ball would still roll if there was no ball in its way (this amount will NEVER be zero meters). If this ball encounters another one, the procedure is repeated (here again the amount of meters still to roll will never be zero).

Input

The input consists of several test cases. The first line in the input contains an integer N specifying the number of test cases (1 <= N <= 10000). The first line of a test case contains the name of the two players separated by one space. A player name is composed of at most 20 letters from the English alphabet (from 'A' through 'Z' and 'a' through 'z'). The next seven lines describe the seven balls in the order they are thrown in the game (first the coche and then the boules thrown by the players according to the rules above). Each line contains four integers X, Y , μ and D representing respectively the starting position of a ball (-1000 <= X, Y <= 1000), its direction (0 <= μ <= 360) and the distance (0 < D <= 100) it will roll if it does not encounter any other ball in its way.

Output

For each test case in the input, your program must produce one line containing the name of the player who won the game and how many points she/he scored separated by a single space.

2
Alex BobNelson
0 0 90 30
0 0 90 20
0 0 0 10
-5 0 0 5
0 40 270 18
0 10 90 13
-1 24 315 1
Alice Alex
0 0 90 50
0 0 90 20
0 0 180 20
-5 0 0 5
0 40 270 18
0 10 90 13
-1 24 315 1
Alex 3
Alice 1

Hint

When comparing numbers, numbers whose absolute difference is less than 0.00001 should be considered equal. Moreover, you may suppose that, in the end of the game, the boule of the loser which is nearest to the coche is not at the same distance of any boule of the winner.

Source

South America 2004