题目描述

给定一个正整数$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}$。

约束条件

• $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$
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入读取：

$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

1
3
2

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

• 令$l=1$，$r=5(=N)$，$t=0$。
• 令$m=3(=\left \lfloor \dfrac{1 \times 1 + 1 \times 5}{1+1} \right \rfloor)$。
• 由于$l \leq 1 < m$，令$r=2(=m-1)$。将$t$增加$1$至$1$。
• 令$m=1(= \left \lfloor \dfrac{1 \times 1 + 1 \times 2}{1+1} \right \rfloor )$。由于$m=1$，令$x_1=1(=t)$并终止。

例如，对于$(c_1,d_1)$的问题，答案为$\\sum_{j=c_i}^{d_i-1} |x_j - x_{j+1}| = |x_1-x_2| = 1$。

示例输入 2

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

示例输出 2

19792
771437738
34191100