← 返回题目列表

Codeforces · 167/D

D. 巫师与道路

中文机器翻译题面 查看原题

在一些国家生活着巫师。他们喜欢建造城市和道路。

国家曾经有 k 个城市,第 j 个城市 (1 ≤ j ≤ k) 位于点 (xj, yj)。决定再创建n-k个城市。第 i 个 (k < i ≤ n) 是在坐标为 (xi, yi) 的点处创建的:

- xi = (a·xi - 1 + b) mod (109 + 9)
- yi = (c·yi - 1 + d) mod (109 + 9)

这里 a、b、c、d 是素数。另外,a≠c,b≠d。

n座城市建成后,巫师们注意到了一些令人惊讶的事情。事实证明,对于每两个不同的城市 i 和 j,xi ≠ xj 且 yi ≠ yj 成立。

城市建成了,是时候修路了!他们决定使用最困难(当然也是最强大)的咒语来修建道路。使用此法术会在 u, v (yu > yv) 城镇之间创建一条道路,当且仅当对于任何严格位于 u, v 点拐角内的城市 w(见下文),存在一个不位于拐角处的城市 s,该城市 s 沿着 x 坐标严格位于 w 和 u 之间,同时 ys > yv。

点 p2(x2, y2), p1(x1, y1) (y1 < y2) 上的角是点 (x, y) 的集合,对于该角点至少满足两个条件之一:

- min(x1, x2) ≤ x ≤ max(x1, x2) 且 y ≥ y1
- y1 ≤ y ≤ y2 且 (x - x2)·(x1 - x2) ≥ 0

显示两个不同角的图片

为了测试该咒语,巫师们会将其应用于x坐标上区间[L,R]内的所有城市。道路建设完成后,国家政府希望选择由道路连接的最大数量的城市对,这样就不会出现两对或更多对城市。您的任务是为每 m 个提供的值 L、R 的变体计算道路施工后此类对的最大数量。请注意,不在x坐标[L,R]区间内的城市不会对道路建设产生任何影响。

输入

第一行包含两个空格分隔的整数 n, k (1 ≤ k ≤ n ≤ 105, k ≤ 30)。接下来的 k 行包含从第一个到第 k 个城市位置点的坐标。第 j 行包含空格分隔的整数对 xj, yj (0 ≤ xj, yj < 109 + 9) — 第 j 个城市的坐标。

下一行包含空格分隔的整数 a、b、c、d (2 ≤ a、b、c、d < 109 + 9)。保证这些数是素数,并且 a ≠ c,b ≠ d。

可以保证,对于每两个不同的城市 i 和 j,xi ≠ xj 且 yi ≠ yj 成立。

下一行包含整数 m (1 ≤ m ≤ 105) — 修建道路的变体数量。接下来的 m 行包含空格分隔的整数对 Li, Ri (0 ≤ Li ≤ Ri < 109 + 9) — 选择城市修建道路的变体。

输出

对于任何一对数字 Li,Ri 将问题的答案打印在一行上。按顺序打印各对的答案,其中各对在输入数据中给出。

示例

输入 #1

6 6
0 0
1 1
2 2
3 3
4 4
5 5
2 3 3 2
4
0 5
1 4
2 3
3 3

输出 #1

3
2
1
0

输入 #2

6 1
0 0
3 5 23917 11
4
0 1000000008
0 10
100 150
200 10000

输出 #2

2
1
0
1

注意

在第一个样本中,道路按照 x 递增的顺序将城市连接成一条链。

在第二个样本中,其余 5 个城市将位于点 (5, 11); (20, 263098); (65、292514823); (200, 76958738); (605、622120197)。