C-小红的数组查询（二）_牛客周赛 Round 95

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 本题与《A.小红的数组查询（一）》共享部分题目背景，但是所求内容不同，我们建议您重新阅读题面。

$\hspace{15pt}$ 小红拿到了一个长度为 $10^{100}$ 的数组，其构成如下：
$\hspace{23pt}\bullet\,$ 数组的第一个元素 $a_1=1$ ；
$\hspace{23pt}\bullet\,$ 对于 $2 \leqq i \leqq 10^{100}$ ， $a_i=(a_{i-1}+d) \bmod p$ 。
$\hspace{15pt}$ 现在小红想知道， $l$ 到 $r$ 之间有多少种不同元素。共有 $q$ 次询问。

输入描述:

第一行输入两个整数 ，表示数组公差、模数。
第二行输入一个整数 ，表示询问次数。
此后  行，第  行输入两个整数 ，表示第  次询问的区间。

输出描述:

对于每一次询问，新起一行，输出一个整数，代表区间内元素的种类数。

示例1

输入

复制

3 4
2
1 2
1 100000000000

输出

复制

2
4

说明

对于第一次询问，、，因此有  和  两种不同的元素。
对于第二次询问，由于该区间元素数量过多，不方便在此展示。但可以证明，一共有  种不同的元素。