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.

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.

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$.