Finding the f-th Time of a Specific Distance Between Two Moving Points

Two friends, A and Y, are moving on a plane. Initially, A is at ( (Ax_0, Ay_0) ) and Y is at ( (Bx_0, By_0) ). They then move along piecewise linear paths. Specifically, A makes ( n ) moves and Y makes ( m ) moves. For A, during the time interval ( [At_{i-1}, At_i] ) (with ( At_0 = 0 )) the movement is a uniform linear motion from ( (Ax_{i-1},Ay_{i-1}) ) to ( (Ax_i,Ay_i) ). Similarly, for Y, during ( [Bt_{i-1}, Bt_i] ) (with ( Bt_0 = 0 )) Y moves uniformly from ( (Bx_{i-1},By_{i-1}) ) to ( (Bx_i,By_i) ).

There are ( q ) queries. Each query gives a floating point number ( c ) and an integer ( f ). For each query, you must determine the time of the ( f\text{-th} ) occurrence (in chronological order) when the distance between A and Y is exactly ( c ).

Special cases:

1. If there are infinitely many times (i.e. an entire time interval during which the distance is constantly ( c )), output ( -2.33 ).
2. If ( f ) is greater than the total number of times when the distance equals ( c ), output ( -4.66 ).

Otherwise, output the time of the ( f\text{-th} ) occurrence.

The answer must be computed with sufficient precision. All formulas are written in ( \LaTeX ) format.

inputFormat

The first line contains three integers: ( n; m ; q ) indicating the number of moves for A, the number of moves for Y, and the number of queries respectively.
The second line contains four floating point numbers: ( Ax_0; Ay_0; Bx_0; By_0 ), the initial coordinates of A and Y.
Then follow ( n ) lines for A’s moves. Each line contains three numbers: ( At_i; Ax_i; Ay_i ) for ( i=1 ) to ( n ), where ( At_i ) is the ending time of the ( i\text{-th} ) move and ( (Ax_i,Ay_i) ) is the destination coordinate.
Then follow ( m ) lines for Y’s moves. Each line contains three numbers: ( Bt_j; Bx_j; By_j ) for ( j=1 ) to ( m ).
Finally, there are ( q ) lines, each containing a floating point number ( c ) and an integer ( f ), representing a query.

outputFormat

For each query, output a single line containing the answer. If there are infinitely many valid times, output ( -2.33 ). If ( f ) exceeds the total occurrences when the distance equals ( c ), output ( -4.66 ). Otherwise, output the time of the ( f\text{-th} ) occurrence (as a floating point number).

sample

1 1 3
0 0 1 0
1 1 0
1 0 0
1 1
1 2
1 3

0.0
1.0
-4.66