在一些国家生活着巫师。他们喜欢建造城市和道路。
国家曾经有 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)。