The village of Kayenne is divided into a square grid. Residents build their houses where the grid lines intersect. The location of each house is described by a pair of $X$ and $Y$ coordinates, where $(0,0)$ is the point at the exact centre of town. Each grid line is exactly the same distance from the grid lines on either side of it. Kayenne stretches out from the centre for $200$ grid lines North, East, South and West. Individuals or families who move to Kayenne are assigned a circular area in which to build their house. This area is centred on a particular grid point and has a radius of $50$. The newcomers are allowed to build their houses on any empty grid point within that circular area (including on the circle boundary).

Some households in Kayenne are Democrat and others are Republican. New households don't get to choose their political affiliations. Instead, their three closest neighbours (determined by the straight line distance between grid locations) vote on their affiliation and the newcomers must abide by the majority decision. Of course, Democrat households always vote that newcomers should be Democrats, and Republican households always vote that they should be Republicans. Occasionally there are ties for the $3^{rd}$ closest neighbour. When this happens, all the neighbours who are the same distance as the $3^{rd}$ closest are also allowed to vote. This can result in an even number of votes, which means that the vote can be tied. In these cases, the newcomers will be Democrats.

The input will contain $10$ test cases.

The first line of each test case will consist of two integers $C_x$ and $C_y$, separated by a space, representing the coordinates of the centre of a newcomer's circular building area $(-150\le C_x,C_y\le 150)$.

The next $100$ lines will each contain two integers $H_x$ and $H_y$ and an uppercase letter $A$ separated by single spaces, representing the coordinates and political affiliation of the existing houses in Kayenne $(-200\le H_x,H_y\le 200,A\in [\mathtt{\text{D}},\mathtt{\text{R}}])$.

Your program must output a number representing the percentage chance (rounded to one decimal place) that a newcomer assigned to this circular building area will end up a Democratic household, assuming they choose their building site randomly from the available sites in their area.

Note that the sample data below contains only $1$ test case with $20$ houses but the test data will contain $10$ test cases with $100$ houses each.

Sample Input

-81 83
15 -198 R
-17 89 R
197 -174 R
-67 89 D
180 -101 D
-78 -173 R
182 121 D
-129 179 R
-100 -53 D
64 -61 D
-123 -152 D
-15 -67 R
20 194 D
125 16 D
133 -28 D
19 -9 R
121 168 D
165 -39 R
-170 -3 D
-27 61 D

Sample Output

88.7

Question Development Team

Sam Scott (Sheridan College)
Kevin Forest (Sheridan College)
Stella Lau (University of Cambridge)
Greg Reid (St. Francis Xavier Secondary School, Mississauga)
Dino Baron (University of Waterloo)
John Ketelaars (ECOO-CS Communications)
David Stermole (ECOO-CS President)

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org