题目描述

给定一个正整数 $N$ 和 $M$ 组正整数对 $(a_0, b_0), \ldots, (a_{M-1}, b_{M-1})$（请注意 $a_i, b_i$ 的下标从 $0$ 开始）。

此外，存在如下定义的非负整数序列 $X=(x_1, \ldots, x_N)$。

• $x_i$ 的确定方式如下：
  1. 令 $l=1, r=N, t=0$。
  2. 令 $m=\left\lfloor \dfrac{a\_{t \bmod M} \times l + b\_{t \bmod M} \times r}{a\_{t \bmod M} + b\_{t \bmod M}} \right\rfloor$（$\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数）。若 $m=i$，则令 $x_i=t$ 并结束步骤。
  3. 若 $l \leq i < m$，则令 $r=m-1$，否则令 $l=m+1$。$t$ 的值加 $1$，回到步骤 2。

对于 $i=1,2,\ldots,Q$，请计算 $\sum_{j=c_i}^{d_i-1} |x_j - x_{j+1}|$ 的值。 在本题的约束下，可以证明答案不会超过 $10^{18}$。

输入格式

输入以如下格式从标准输入给出。

$N$ $M$
$a_0$ $b_0$
$\vdots$
$a_{M-1}$ $b_{M-1}$
$Q$
$c_1$ $d_1$
$\vdots$
$c_Q$ $d_Q$

输出格式

输出 $Q$ 行。第 $x$ 行输出对应 $i=x$ 的问题答案。

样例 1

输入

5 1
1 1
3
1 2
2 4
3 5

输出

1
3
2

样例 2

输入

1000000000000000 2
15 9
9 15
3
100 10000
5000 385723875
150 17095708

输出

19792
771437738
34191100

说明/提示

限制条件

• $2 \leq N \leq 10^{15}$
• $1 \leq M \leq 100$
• $1 \leq a_i, b_i \leq 1000$
• $\max \left( \dfrac{a\_i}{b\_i}, \dfrac{b\_i}{a\_i} \right) \leq 2$
• $1 \leq Q \leq 10^4$
• $1 \leq c_i < d_i \leq N$
• 所有输入均为整数

样例解释 1

$X=(1,2,0,1,2)$。例如，$x_1$ 的确定过程如下：

• 令 $l=1, r=5(=N), t=0$。
• 令 $m=3\left(=\left\lfloor \dfrac{1 \times 1 + 1 \times 5}{1+1} \right\rfloor\right)$。
• 因为 $l \leq 1 < m$，所以 $r=2(=m-1)$，$t$ 增加到 $1$。
• 令 $m=1\left(= \left\lfloor \dfrac{1 \times 1 + 1 \times 2}{1+1} \right\rfloor \right)$。$m=1$，所以 $x_1=1(=t)$，过程结束。

对于 $(c_i, d_i)$，例如 $(c_1, d_1)$，答案为 $\sum\_{j=c\_i}^{d\_i-1} |x\_j - x\_{j+1}| = |x\_1-x\_2| = 1$。

由 ChatGPT 4.1 翻译