{"raw_statement":[{"iden":"problem statement","content":"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$).\nWe have the following sequence of non-negative integers $X=(x_1,\\ldots,x_N)$.\n\n*   $x_i$ is determined as follows.\n    1.  Let $l=1$, $r=N$, and $t=0$.\n    2.  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.\n    3.  If $l \\leq i \\lt m$, let $r=m-1$; otherwise, let $l=m+1$. Increment $t$ by $1$ and return to step 2.\n\nFind $\\sum_{j=c_i}^{d_i-1} |x_j - x_{j+1}|$ for $i=1,2,\\ldots,Q$.  \nIt can be proved that the answers are at most $10^{18}$ under the constraints of this problem."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 10^{15}$\n*   $1 \\leq M \\leq 100$\n*   $1 \\leq a_i,b_i \\leq 1000$\n*   $\\max \\left (\\dfrac{a_i}{b_i},\\dfrac{b_i}{a_i}\\right ) \\leq 2$\n*   $1 \\leq Q \\leq 10^4$\n*   $1 \\leq c_i \\lt d_i \\leq N$\n*   All values in the input are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $M$\n$a_0$ $b_0$\n$\\vdots$\n$a_{M-1}$ $b_{M-1}$\n$Q$\n$c_1$ $d_1$\n$\\vdots$\n$c_Q$ $d_Q$"},{"iden":"sample input 1","content":"5 1\n1 1\n3\n1 2\n2 4\n3 5"},{"iden":"sample output 1","content":"1\n3\n2\n\nWe have $X=(1,2,0,1,2)$. For example, $x_1$ is determined as follows.\n\n*   Let $l=1$, $r=5(=N)$, and $t=0$.\n*   Let $m=3(=\\left \\lfloor \\dfrac{1 \\times 1 + 1 \\times 5}{1+1} \\right \\rfloor)$.\n*   Since $l \\leq 1 \\lt m$, let $r=2(=m-1)$. Increment $t$ by $1$ to $1$.\n*   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.\n\nThe 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$."},{"iden":"sample input 2","content":"1000000000000000 2\n15 9\n9 15\n3\n100 10000\n5000 385723875\n150 17095708"},{"iden":"sample output 2","content":"19792\n771437738\n34191100"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}