U497098 YXM的刷题计划

``` 那必须得刷啊，不刷咋办呢 --YXM ```

YXM是FY1Z的一名数学老师，作为一名优秀的教师，他会给学生布置很多试卷，既然布置了，YXM就需要对这些试卷一一进行讲解。 已知某天的某张试卷中有 $n$ 道题目需要讲，每道题的方法序列 $s_i$ 都是一个 $[\ 1\ ,\ 10^6\ ]$ 范围内的整数，对于两道方法序列分别为 $s_i,s_j$ 的题，如果$f(s_i)=s_j$，则称题目 $j$ 是题目 $i$ 的**弱化版**，其中 $f(x)=kx+b$ 。 那么，如果YXM讲了第 $i$ 道题，那么对于该题的弱化版，YXM只需要简单提两句，消耗的时间为 $0$，否则其消耗时间为 $1$。 YXM会向你提出 $T$ 个问题，每个问题形如，如果我**只讲**第 $x\sim y$题，那么我需要消耗多少时间？ 值得注意的是，若YXM只是"简单提两句"，也算作其"讲了"。

共 $T+2$ 行，第一行包含 $n,T,k,b$ 四个数。 第二行包含 $n$ 个数，表示 $s_1$ 到 $s_n$ 。 第三行到第 $T+2$ 行，每行包含两个数 $x,y$ ，表示一个询问，具体含义如题目描述。

共$T$行，每行一个数，表示对应询问的答案

| 测试点编号 | $n$ | $T$ | $k,b$ | | :-----------: | :-----------: | :-----------: | :-----------: | | $1$ | $\le10^2$ | $\le10^2$ | $\le20$ | | $2$ | $\le10^2$ | $\le10^2$ | $\le20$ | | $3$ | $\le10^3$ | $\le10^3$ | $\le20$ | | $4$ | $\le10^3$ | $\le10^3$ | $\le20$ | | $5$ | $\le10$ | $\le10^5$ | $\le20$ | | $6$ | $\le10^5$ | $\le10$ | $\le20$ | | $7$ | $\le10^5$ | $\le10^5$ | $k=1,b=0$ | | $8$ | $\le10^4$ | $\le10^4$ | $\le20$ | | $9$ | $\le10^5$ | $\le10^5$ | $\le20$ | | $10$ | $\le10^5$ | $\le10^5$ | $\le20$ | 数据保证 $k,b\ge0$ 且为整数 ### 样例解释 根据题意，题目3是题目1的弱化版，题目5是题目2的弱化版，题目4是题目5的弱化版。 1. 对于询问1，需要消耗时间的题目有第1，3题。 1. 对于询问2，需要消耗时间的题目有第2，3，4题。 1. 对于询问3，需要消耗时间的题目有第2，3题。 1. 对于询问4，需要消耗时间的题目有第1，2题。