舱带覆写

• 输入文件：big.in
• 输出文件：big.out

题目背景

远航母舰的外壳被划分成一条长度为 n 的线性舱带，位置编号为 1, 2, ..., n。初始时，所有位置的颜色均为 0。

维护中心会按时间顺序执行 m 条覆写指令。第 i 条指令不会直接给出区间端点，而是由控制参数 p, q 和当前编号 i 自动生成两个锚点：

• a_i = ((i × p + q) mod n) + 1
• b_i = ((i × q + p) mod n) + 1

随后，系统会把区间 [min(a_i, b_i), max(a_i, b_i)] 上的所有位置都覆写成颜色 i。

所有指令执行结束后，观测员会对若干区间进行统计，想知道每段舱带中最终一共出现了多少种不同颜色。

题目描述

给定整数 n, m, p, q，对每个 i = 1, 2, ..., m 执行以下操作：

1. 计算两个位置 a_i = ((i × p + q) mod n) + 1，b_i = ((i × q + p) mod n) + 1；
2. 设 l_i = min(a_i, b_i)，r_i = max(a_i, b_i)；
3. 将区间 [l_i, r_i] 上的所有位置都覆写成颜色 i。

全部覆写结束后，有 Q 次询问。每次给出一个区间 [l, r]，你需要回答最终状态下这段区间中一共出现了多少种不同颜色。

注意：

• 颜色 0 表示该位置从未被任何指令覆写；
• 如果区间内出现了若干颜色相同的位置，这种颜色只计算一次。

输入格式

第一行四个整数 n, m, p, q，含义如上。

第二行一个整数 Q，表示询问个数。

接下来 Q 行，每行两个整数 l, r，表示一次询问。

输出格式

输出共 Q 行。

第 i 行输出一个整数，表示第 i 次询问的答案。

输入输出样例

样例 1

输入：

8 5 2 5
4
1 8
1 3
2 6
7 8

输出：

3
2
2
1

样例解释

执行全部 5 次覆写后，最终颜色数组为：

1 3 3 5 5 5 5 5

因此：

• 区间 [1, 8] 中出现了颜色 1, 3, 5，答案为 3；
• 区间 [1, 3] 中出现了颜色 1, 3，答案为 2；
• 区间 [2, 6] 中出现了颜色 3, 5，答案为 2；
• 区间 [7, 8] 中只有颜色 5，答案为 1。

数据范围

对于全部数据，满足：

• 1 ≤ n, m ≤ 10⁶
• 1 ≤ Q ≤ 2 × 10⁵
• 1 ≤ p, q ≤ 10⁹
• 1 ≤ l ≤ r ≤ n

评测共 20 个测试点，每个测试点 5 分，互不捆绑。