Problem Statement

You are given a positive integer N, and M pairs of positive integers: $(a_0,b_0),\ldots,(a_{M-1},b_{M-1}) ($note that a_i and b_i start with index 0).
We have the following sequence of $non-negative integers X=(x_1,\ldots,x_N)$.

• x_i is determined as follows.
• Let l=1, r=N, and t=0.
• Let $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$ is the greatest integer not exceeding x). If m=i, let x_i=t and terminate.
• If $l \leq i \lt m$, let r=m-1; otherwise, let l=m+1. Increment t by 1 and return to step 2.

Find $\sum_{j=c_i}^{d_i-1} |x_j - x_{j+1}|$ for $i=1,2,\ldots,Q$.
It can be proved that the answers are at most 10^{18} under the constraints of this problem.

Input

The input is given from Standard Input in the following format:
N M
a_0 b_0
$\vdots$
a_{M-1} b_{M-1}
Q
c_1 d_1
$\vdots$
c_Q d_Q

Output

Print Q lines. The x-th line should contain the answer to the question for i=x.

Constraints

• $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 \lt d_i \leq N$
• All values in the input are integers.

Sample Input 1

5 1
1 1
3
1 2
2 4
3 5

Sample Output 1

1
3
2

We have X=(1,2,0,1,2). For example, x_1 is determined as follows.

• Let l=1, r=5(=N), and t=0.
• Let $m=3(=\left \lfloor \dfrac{1 \times 1 + 1 \times 5}{1+1} \right \rfloor)$.
• Since $l \leq 1 \lt m$, let r=2(=m-1). Increment t by 1 to 1.
• Let $m=1(= \left \lfloor \dfrac{1 \times 1 + 1 \times 2}{1+1} \right \rfloor ). Since m=1$, let x_1=1(=t) and terminate.

The answer to the question for (c_1,d_1), for example, is $\sum_{j=c_i}^{d_i-1} |x_j - x_{j+1}| = |x_1-x_2| = 1$.

Sample Input 2

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

Sample Output 2

19792
771437738
34191100

见题面 Input 部分

见题面 Output 部分