给定 $N,M$ 以及 $M$ 个二元组 $(a_0,b_0),...,(a_{M-1},b_{M-1})$。

对于任意的 $i\in[1,n]$，有 $\max(\dfrac{a_i}{b_i},\dfrac{b_i}{a_i})\leqslant 2$。

生成序列 $\{X_{N}\}$，生成方式如下：

• 首先有 $l=1,r=N,t=0$；

• 令 $m=\lfloor\dfrac{a_{t\bmod M}\times l+b_{t\bmod M}\times r}{a_{t\bmod M}+b_{t\bmod M}}\rfloor$，若 $m=i$ 则令 $X_i=t$ 并结束；

• 若 $l\leqslant i<m$，则令 $r=m-1$，柔则令 $l=m+1$，令 $t\leftarrow t+1$ 并返回第二步。

有 $Q$ 个询问，每次给定区间 $(c_i,d_i)$，询问 $\sum\limits_{j=c_i}^{d_i-1}|X_j-X_{j+1}|$。

translated by cszyf