Half-Rays

Time limit2sMemory limit128 MB

Summary

Given N half-rays defined by lines restricted to x>0, answer online queries with forced XOR decoding that ask for the maximum x-coordinate where a query line intersects any half-ray, using a Li Chao-style convex hull technique.

Level: Hard8 of 10
Topics: Divide and conquer, Binary search, Geometry, Math
Solved: No attempts yet

Problem

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.

Input

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.

Output

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.

Constraints

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

Examples1

Example 1

Input

Expected output

0.75000000
No cross
1.00000000