Problem J: Secret Operation

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 George’s 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 George’s 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.

Input

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

Time R
L
MaryX₁ MaryY₁ MaryT₁
MaryX₂ MaryY₂ MaryT₂
...
MaryX_L MaryY_L MaryT_L
M
GeorgeX₁ GeorgeY₁ GeorgeT₁
GeorgeX₂ GeorgeY₂ GeorgeT₂
...
GeorgeX_M GeorgeY_M GeorgeT_M
N BlockSX₁ BlockSY₁ BlockTX₁ BlockTY₁
BlockSX₂ BlockSY₂ BlockTX₂ BlockTY₂
...
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, MaryY_i) to (MaryX_i+1, MaryY_i+1) straight and at a constant speed during the time between MaryT_i and MaryT_i+1, for each 1 ≤ i ≤ L - 1. The following constraints apply: 2 ≤ L ≤ 20, MaryT₁ = 0 and MaryT_L = Time, and MaryT_i < MaryT_i+1 for any 1 ≤ i ≤ L - 1.

The description of George's move is given in the same way with the same constraints, following Mary's. In addition, (GeorgeX_j, GeorgeY_j ) and (GeorgeX_j+1, GeorgeY_j+1) do not coincide for any 1 ≤ j ≤ M - 1. In other words, George is always moving in some direction.

Finally, there comes the information of the obstacles. Each obstacle has a rectangular shape occupying (BlockSX_k, BlockSY_k) to (BlockTX_k, BlockTY_k). No obstacle touches or crosses with another. The number of obstacles ranges from 0 to 20 inclusive.

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.

Output

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 .

Sample Input

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

Output for the Sample Input

50

---