/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 900 点
問題文
正整数 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 は以下の手順で定まる。
- l=1,r=N,t=0 とする。
- 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 として手順を終了する。
- l \leq i \lt 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 \lt 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 \lt 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_i,d_i) への答えは、例えば (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
Score : 900 points
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.
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