Mary Ice is a member of a spy group. She is about to carry out a secret operation with her colleague.

She has got into a target place just now, but unfortunately the colleague has not reached there yet. She needs to hide from her enemy George Water until the colleague comes. Mary may want to make herself appear in Georgefs sight as short as possible, so she will give less chance for George to find her.

You are requested to write a program that calculates the time Mary is in Georgefs sight before her colleague arrives, given the information about moves of Mary and George as well as obstacles blocking their sight.

Read the Input section for the details of the situation.

The input consists of multiple datasets. Each dataset has the following format:

*Time R*

*L*

*MaryX*_{1} *MaryY*_{1} *MaryT*_{1}

*MaryX*_{2} *MaryY*_{2} *MaryT*_{2}

...

*MaryX*_{L} *MaryY*_{L} *MaryT*_{L}

*M*

*GeorgeX*_{1} *GeorgeY*_{1} *GeorgeT*_{1}

*GeorgeX*_{2} *GeorgeY*_{2} *GeorgeT*_{2}

...

*GeorgeX*_{M} *GeorgeY*_{M} *GeorgeT*_{M}

*N*
*BlockSX*_{1} *BlockSY*_{1} *BlockTX*_{1} *BlockTY*_{1}

*BlockSX*_{2} *BlockSY*_{2} *BlockTX*_{2} *BlockTY*_{2}

...

*BlockSX*_{N} *BlockSY*_{N} *BlockTX*_{N} *BlockTY*_{N}

The first line contains two integers. Time (0 ≤ *Time* ≤ 100) is the time Mary's colleague reaches the
place. *R* (0 < *R* < 30000) is the distance George can see - he has a sight of this distance and of 45
degrees left and right from the direction he is moving. In other words, Mary is found by him if and only
if she is within this distance from him and in the direction different by not greater than 45 degrees from
his moving direction and there is no obstacles between them.

The description of Mary's move follows. Mary moves from (*MaryX _{i}*,

The description of George's move is given in the same way with the same constraints, following Mary's.
In addition, (*GeorgeX _{j}*,

Finally, there comes the information of the obstacles. Each obstacle has a rectangular shape occupying
(*BlockSX _{k}*,

All the coordinates are integers not greater than 10000 in their absolute values. You may assume that, if
the coordinates of Mary's and George's moves would be changed within the distance of 10^{-6}, the solution would be changed by not greater than 10^{-6}.

The last dataset is followed by a line containing two zeros. This line is not a part of any dataset and should not be processed.

For each dataset, print the calculated time in a line. The time may be printed with any number of digits after the decimal
point, but should be accurate to 10^{-4} .

50 100 2 50 50 0 51 51 50 2 0 0 0 1 1 50 0 0 0

50

Source: ACM-ICPC Japan Alumni Group Summer Camp 2009
, Day 3, Tokyo, Japan, 2009-09-20

http://jag-icpc.org/

http://jag-icpc.org/