点与比较

题目描述

注意特殊的输入格式。

在 $xy$ 平面上有 $N$ 个点 $(X_i,Y_i)$。这些点在输入中给出。

另外给出 $Q$ 对整数 $(A_j,B_j)$。

定义 $f(A_j,B_j)$ 为满足 $Y_i \ge A_j \times X_i + B_j$ 的下标 $i$ 的个数。

求 $\displaystyle \sum_{j=1}^{Q} f(A_j,B_j)$。

由于 $Q$ 非常大，$(A_j,B_j)$ 不会直接给出。

取而代之，给出 $G_0$、$R_a$ 和 $R_b$，$(A_j,B_j)$ 按如下方式生成：

首先，对于 $n \ge 0$，定义 $G_{n+1} = (48271 \times G_n) \mod (2^{31}-1)$。

对于 $j=1,2,\dots,Q$，按如下方式生成 $(A_j,B_j)$：

$A_j = -R_a + (G_{3j - 2} \mod (2 \times R_a + 1) )$

$B_j = -R_b + ((G_{3j - 1} \times (2^{31}-1) + G_{3j}) \mod (2 \times R_b + 1) )$

由上述方法可知，$A_j$ 和 $B_j$ 满足以下约束：

$-R_a \le A_j \le R_a$

$-R_b \le B_j \le R_b$

输入格式

输入按以下格式从标准输入给出：

N
X_1 Y_1
X_2 Y_2
⋮
X_N Y_N
Q
G_0 R_a R_b

输出格式

输出答案（整数）。

样例

7
2 -2
-1 -2
0 1
2 1
-2 2
1 2
0 -1
10
1 5 5

36

该输入包含 10 个问题。生成的 $(A_j,B_j)$ 为 $(-2,4),(0,2),(-4,-2),(4,-5),(3,1),(-1,3),(2,-5),(3,-1),(3,5),(3,-2)$。

数据范围

• 输入均为整数。
• $1 \le N \le 5000$
• $1 \le Q \le 10^7$
• $|X_i|, |Y_i| \le 10^8$
• $(X_i,Y_i)$ 互不相同。
• $0 \le G_0 \lt (2^{31}-1)$
• $0 \le R_a \le 10^8$
• $0 \le R_b \le 10^{16}$