반직선

N개의 반직선이 주어진다. 각 반직선은 y축 위의 점에서 시작하며, y축과 평행하지 않다. i번째 반직선은 직선 y = A_i x + B_i 중 x > 0인 부분이다.

Q개의 질문에 답하라. j번째 질문에서 주어진 직선 y = C_j x + D_j와 N개의 반직선이 만나는 점들을 모두 생각한다. 그 교점들의 x좌표 중 최댓값을 구하라.

첫 줄에 반직선의 개수 N이 주어진다. 다음 N줄에는 각 반직선의 계수 A_i, B_i가 공백으로 구분되어 주어진다.

그다음 줄에 질문의 개수 Q가 주어진다. 다음 Q줄에는 두 정수 E, F가 주어진다.

현재 질문이 첫 번째 질문이거나, 직전 질문의 직선과 N개의 반직선 사이에 교점이 하나 이상 있었다면 C_j = E, D_j = F이다. 그렇지 않다면 C_j = E XOR (2^29 - 1), D_j = F XOR (2^29 - 1)이다. 여기서 XOR는 비트 단위 배타적 논리합 연산이다.

각 질문마다 한 줄에 답을 출력한다. 답은 질문에서 주어진 직선과 N개의 반직선이 이루는 교점들의 x좌표 중 최댓값이며, 소수점 아래 적어도 6자리까지 출력해야 한다.

교점이 하나도 없다면 No cross를 출력한다.

• 입력되는 모든 값은 정수이다.
• -2,000,000,000 < A_i, B_i, C_j, D_j < 2,000,000,000
• 모든 i, j (i ≠ j)에 대해 A_i ≠ A_j
• 모든 i, j에 대해 A_i ≠ C_j
• 모든 i, j에 대해 B_i ≠ D_j
• 1 ≤ N, Q ≤ 50,000