Half-Rays

You are given N half-rays. Each half-ray starts from a point on the y-axis and is not parallel to the y-axis. The i-th half-ray is the part of the line y = A_i x + B_i defined only for x > 0.

Answer Q queries. In the j-th query, consider the line y = C_j x + D_j and all intersection points it makes with the N half-rays. Find the maximum x-coordinate among those intersections.

The first line contains the number of half-rays N. Each of the next N lines contains two integers A_i and B_i, the coefficients of one half-ray.

The next line contains the number of queries Q. Each of the next Q lines contains two integers E and F.

If this is the first query, or if the line from the previous query intersected at least one of the N half-rays, then C_j = E and D_j = F. Otherwise, C_j = E XOR (2^29 - 1) and D_j = F XOR (2^29 - 1). Here XOR is the bitwise exclusive-or operation.

For each query, print one line. The answer is the maximum x-coordinate among all intersections between the query line and the N half-rays, printed with at least 6 digits after the decimal point.

If there is no intersection, print No cross.

• Every input value is an integer.
• -2,000,000,000 < A_i, B_i, C_j, D_j < 2,000,000,000
• For all i, j with i ≠ j, A_i ≠ A_j
• For all i, j, A_i ≠ C_j
• For all i, j, B_i ≠ D_j
• 1 ≤ N, Q ≤ 50,000