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&lt;i<=n $ ) was created at a point with coordinates ( $ x_{i} $ , $ y_{i} $ ): - $ x_{i}=(a·x_{i-1}+b) mod (10^{9}+9) $ - $ y_{i}=(c·y_{i-1}+d) mod (10^{9}+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}&gt;y_{v} $ . A corner on the points $ p_{2} $ ( $ x_{2} $ , $ y_{2} $ ), $ p_{1} $ ( $ x_{1} $ , $ y_{1} $ ) ( $ y_{1}&lt;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.

输入输出格式

输入格式

The first line contains two space-separated integers $ n $ , $ k $ ( $ 1<=k<=n<=10^{5} $ , $ 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}&lt;10^{9}+9 $ ) — coordinates of the $ j $ -th city. The next line contains space-separated integers $ a,b,c,d $ ( $ 2<=a,b,c,d&lt;10^{9}+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<=10^{5} $ ) — 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}&lt;10^{9}+9 $ ) — the variants of choosing the cities to build the roads.

输出格式

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.

输入输出样例

输入样例 #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

说明

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) $ .

题意翻译

在某些国家里住着巫师。他们喜欢建造城市和道路。 这个国家过去有 $ k $ 个城市，第 $ j $ 个城市（$ 1<=j<=k $）位于一个点（$ x_{j} $，$ y_{j} $）。决定创建另外 $ n-k $ 个城市。第 $ i $ 个城市（$ k<i<=n $）的坐标为（$ x_{i} $，$ y_{i} $）： $ x_{i}=(a·x_{i-1}+b) mod (10^{9}+9) $ $ y_{i}=(c·y_{i-1}+d) mod (10^{9}+9) $ 其中，$ a $，$ b $，$ c $，$ d $ 都是质数。并且，$ a≠c，b≠d $。 在建造完所有的 $ n $ 个城市之后，巫师们发现了一些惊人的事情。对于任意两个不同的城市 $ i $ 和 $ j $，都有 $ x_{i}≠x_{j} $ 且 $ y_{i}≠y_{j} $。 城市已经建好了，现在是时候建造道路了！决定使用最困难的（当然也是最强大的）咒语来建造道路。使用这个咒语，如果在 $ u $，$ v $（$ y_{u} $ > $ y_{v} $）两个城镇之间存在一个点 $ w $，并且在 $ w $ 这个角落内还有一个城市 $ 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})<=x<=max(x_{1},x_{2}) $ 并且 $ y>=y_{1} $ $ y_{1}<=y<=y_{2} $ 且 $ (x-x_{2})·(x_{1}-x_{2})>=0 $