题目描述

给定 N 条射线，它们的起点都在 Oy 轴上，并且都不与 Oy 轴平行。第 i 条射线用方程

表示，但它只在 x>0 的半平面内有效。

接下来有 Q 次询问。每次询问给出一条直线

你需要回答：这条直线与给定 N 条射线中的某一条相交时，交点横坐标的最大值是多少。

输入格式

第一行输入一个正整数 N。

接下来 N 行，每行两个整数 Ai, Bi，表示一条射线。

接下来一行输入一个正整数 Q。

再接下来 Q 行，每行给出两个整数 E, F。当前询问对应直线的系数定义如下：

• 如果上一条询问对应的直线与某条射线有交点，或者这是第一条询问，则
  • Cj = E
  • Dj = F
• 否则：
  • Cj = E ^ (2^29 - 1)
  • Dj = F ^ (2^29 - 1)

其中 ^ 表示按位异或。

输出格式

对每次询问：

• 若当前直线与至少一条给定射线相交，输出交点横坐标的最大值，至少保留 6 位小数；
• 否则输出 No cross。

数据范围

• 输入中的所有数均为整数
• -10^9 < Ai,Bi,Ci,Di < 10^9
• 所有 Ai 两两不同
• 每个 Cj 都不等于任一 Ai
• 每个 Dj 都不等于任一 Bi

子任务

• 子任务 1（15 分）：0 < N,Q < 2001
• 子任务 2（20 分）：0 < N,Q < 30001，且对所有 j 有 Cj = 0
• 子任务 3（25 分）：0 < N,Q < 30001，且每条询问直线都至少与一条射线相交，并且至少有一个 Cj != 0
• 子任务 4（30 分）：0 < N,Q < 30001
• 子任务 5（10 分）：0 < N,Q < 50001

评分说明

某个子任务只有在其所有测试点全部通过时才能得到对应分数。

样例

输入

2
4 2
-1 0
3
-5 3
0 1
-5 3

输出

0.75000000
No cross
1.00000000