CF167D.Wizards and Roads

In some country live wizards. They love to build cities and roads.

The country used to have k cities, the j-th city (1 ≤ j ≤ k) was located at a point (x__j, y__j). It was decided to create another n - k cities. And the i-th one (k < i ≤ n) was created at a point with coordinates (x__i, y__i):

• x__i = (a·x__i - 1 + b) mod (109 + 9)
• y__i = (c·y__i - 1 + d) mod (109 + 9)

Here a, b, c, d are primes. Also, a ≠ c, b ≠ d.

After the construction of all n cities, the wizards have noticed something surprising. It turned out that for every two different cities i and j, x__i ≠ x__j and y__i ≠ y__j holds.

The cities are built, it's time to build roads! It was decided to use the most difficult (and, of course, the most powerful) spell for the construction of roads. Using this spell creates a road between the towns of u, v (y__u > y__v) if and only if for any city w which lies strictly inside the corner at the point u, v (see below), there is a city s that does not lie in the corner, which is located along the x-coordinate strictly between w and u and simultaneously y__s > y__v.

A corner on the points _p_2(_x_2, _y_2), _p_1(_x_1, _y_1) (_y_1 < _y_2) is the set of points (x, y), for which at least one of the two conditions is fulfilled:

• min(_x_1, _x_2) ≤ x ≤ max(_x_1, _x_2) and y ≥ _y_1
• _y_1 ≤ y ≤ _y_2 and (x - _x_2)·(_x_1 - _x_2) ≥ 0

The pictures showing two different corners

In order to test the spell, the wizards will apply it to all the cities that lie on the x-coordinate in the interval [L, R]. After the construction of roads the national government wants to choose the maximum number of pairs of cities connected by the road, so that no city occurs in two or more pairs. Your task is for each m offered variants of values L, R to calculate the maximum number of such pairs after the construction of the roads. Please note that the cities that do not lie in the interval [L, R] on the x-coordinate, do not affect the construction of roads in any way.

在某个国家居住着巫师。他们热衷于建造城市和道路。

该国原本有 $k$ 座城市，第 $j$ 座城市（$1 \le j \le k$）位于点 $(x_j, y_j)$。随后决定再新建 $n - k$ 座城市，其中第 $i$ 座城市（$k < i \le n$）的坐标 $(x_i, y_i)$ 按如下递推式生成：

• $x_i = (a \cdot x_{i-1} + b) \bmod (10^9 + 9)$
• $y_i = (c \cdot y_{i-1} + d) \bmod (10^9 + 9)$

其中 $a, b, c, d$ 均为质数，且满足 $a \ne c$、$b \ne d$。

当全部 $n$ 座城市建成之后，巫师们发现了一个惊人的现象：对任意两个不同的城市 $i$ 和 $j$，均有 $x_i \ne x_j$ 且 $y_i \ne y_j$。

城市已建成，现在是修建道路的时候了！人们决定采用最困难（当然也是最强大）的咒语来修建道路。该咒语会在城市 $u$ 与 $v$ 之间修建一条道路（要求 $y_u > y_v$），当且仅当：对任意严格位于以点 $u, v$ 构成的“角”内部的城市 $w$（定义见下文），都存在某个城市 $s$，满足：

• $s$ 不在此“角”内；
• $s$ 的 $x$ 坐标严格介于 $w$ 与 $u$ 之间；
• 且 $y_s > y_v$。

对于两点 $p_2(x_2, y_2)$、$p_1(x_1, y_1)$（其中 $y_1 < y_2$）所构成的“角”，其定义为所有满足以下两个条件中至少一个的点 $(x, y)$ 的集合：

• $\min(x_1, x_2) \le x \le \max(x_1, x_2)$ 且 $y \ge y_1$
• $y_1 \le y \le y_2$ 且 $(x - x_2)(x_1 - x_2) \ge 0$

展示两种不同“角”的示意图

为测试该咒语，巫师们将它施加于所有 $x$ 坐标落在区间 $[L, R]$ 内的城市上。道路建成后，国家政府希望从中选出尽可能多的城市对，使得每对城市由一条道路直接相连，且任意城市至多出现在一个被选中的对中（即匹配）。你的任务是：对给定的 $m$ 组 $L, R$ 的取值，分别计算道路修建完成后所能得到的最大匹配数。请注意：所有 $x$ 坐标不在区间 $[L, R]$ 内的城市，在道路修建过程中完全不产生任何影响。

The first line contains two space-separated integers n, k (1 ≤ k ≤ n ≤ 105, k ≤ 30). Next k lines contain coordinates of the cities' location points from the first to the k-th one. The j-th line contains space-separated pair of integers x__j, y__j (0 ≤ x__j, y__j < 109 + 9) — coordinates of the j-th city.

The next line contains space-separated integers a, b, c, d (2 ≤ a, b, c, d < 109 + 9). It is guaranteed that those numbers are prime and also that a ≠ c, b ≠ d.

It's guaranteed, that for every two different cities i and j, x__i ≠ x__j and y__i ≠ y__j holds.

The next line contains integer m (1 ≤ m ≤ 105) — the number of variants to build the roads. Next m lines contain pairs of space-separated integers L__i, R__i (0 ≤ L__i ≤ R__i < 109 + 9) — the variants of choosing the cities to build the roads.

第一行包含两个以空格分隔的整数 $n$、$k$（$1 ≤ k ≤ n ≤ 10^5$，$k ≤ 30$）。接下来的 $k$ 行依次给出第 $1$ 个至第 $k$ 个城市的坐标。第 $j$ 行包含一对以空格分隔的整数 $x_j$、$y_j$（$0 ≤ x_j,\,y_j < 10^9 + 9$），表示第 $j$ 个城市的坐标。

下一行包含四个以空格分隔的整数 $a$、$b$、$c$、$d$（$2 ≤ a,\,b,\,c,\,d < 10^9 + 9$）。保证这些数均为质数，且满足 $a ≠ c$、$b ≠ d$。

保证对任意两个不同的城市 $i$ 和 $j$，均有 $x_i ≠ x_j$ 且 $y_i ≠ y_j$。

下一行包含一个整数 $m$（$1 ≤ m ≤ 10^5$）—— 表示修建道路的方案数量。接下来的 $m$ 行每行包含一对以空格分隔的整数 $L_i$、$R_i$（$0 ≤ L_i ≤ R_i < 10^9 + 9$）—— 表示选择城市修建道路的方案范围。

For any pair of numbers L__i, R__i print the answer to the problem on a single line. Print the answers for the pairs in the order, in which the pairs are given in the input data.

对于每一对数字 $L_i$、$R_i$，请在单独一行输出该问题的答案。请按照输入数据中给出这些数对的顺序输出对应答案。

In the first sample the roads connect the cities in a chain in the order of increasing of x.

In the second sample the remaining 5 cities will be located at points (5,  11); (20,  263098); (65,  292514823); (200,  76958738); (605,  622120197).

在第一个样例中，道路按 $x$ 坐标递增的顺序将城市连接成一条链。

在第二个样例中，剩余的 5 个城市将位于以下坐标点：$(5,\,11)$；$(20,\,263098)$；$(65,\,292514823)$；$(200,\,76958738)$；$(605,\,622120197)$。