P15039 「chaynOI R2 T4」无限的信息

flow 收到了一大串信息！ 具体来说，flow 一开始有 $n$ 条信息，每条信息是一个**无限长的**数字序列，构成了数据库 $S=\{d_1,d_2,\dots,d_n\}$。 每条信息以 $d_i=f(l_i,r_i)$ 给出，其中 $f(l,r)$ 表示将 $l\sim r$ 的数字不断重复写出的序列，比如 $f(11,14)=\{11,12,13,14,11,12,13,14,11\dots\}$。 定义两条信息 $d,d'$ 的相似性为 $F(d,d')=\max\limits_{x\in \N}\left(\lim\limits_{n\to +\infty}\dfrac{\sum\limits_{i=1}^n [d_i=d'_{i+x}]}{n}\right)$。可以证明，这个极限会收敛到一个确定的数字，其中 $[P]$ 为艾弗森括号，当 $P$ 为真是值为 $1$，否则为 $0$。 现在 flow 又收到了 $q$ 条信息 $D=f(L,R)$，由于消息在不断的更新迭代，所以 flow 保证这次的消息 $R$ 不小于数据库中**所有**消息的 $r_i$。 flow 想要请你求出 $\max\limits_{i=1}^nF(D,d_i)$ 的值，以便继续分析。

第一行输入两个正整数 $n,q$。 接下来 $n$ 行，每行两个正整数 $l_i,r_i$。 接下来 $q$ 行，每行两个正整数 $L,R$。

共 $q$ 行，每行输出一个小数，表示答案。 你的结果与标准答案的绝对误差不超过 $10^{-13}$ 即被认为正确。

### 样例 2 解释 $d_1=\{2,3,2,3,2,3,\dots\}$，$d_2=\{1,2,3,1,2,3,\dots\}$。 对于第一次询问，$D=\{2,3,2,3,2,3,\dots\}$，与 $d_1$ 相等，所以易得 $\max\limits_{i=1}^nF(D,d_i)=F(D,d_1)=1$。 对于第二次询问，$D=\{2,3,4,2,3,4,\dots\}$，可以证明，$F(D,d_1)=\frac{1}{3}(x=0),F(D,d_2)=\frac{2}{3}(x=1)$，所以 $\max\limits_{i=1}^nF(D,d_i)=F(D,d_2)=\frac{2}{3}$。 对于第三次询问，可以证明，$F(D,d_1)=F(D,d_2)=\frac{1}{5}$，所以 $\max\limits_{i=1}^nF(D,d_i)=\frac{1}{5}$。 ### 数据范围 对于 $100\%$ 的数据，保证 $1\le n\le 10^6$，$1\le q\le10^5$，$1\le l_i\le r_i\le8\times10^5$，$1\le L\le R\le 10^6$，$r_i\le R$。 请注意可能存在的精度问题。 + Subtask1(5pts)：$n,q,R\le 20$。 + Subtask2(5pts)：$n,q,R\le 80$。 + Subtask3(10pts)：$n,q,R\le 1000$。 + Subtask4(8pts)：$L \le l_i$。 + Subtask5(12pts)：$L \ge l_i$。 + Subtask6(10pts)：$n,R\le10^5,q\le5000$。 + Subtask7(17pts)：$n,R\le3\times10^5,q\le20000$。 + Subtask8(8pts)：$R\le3\times10^5,q\le30000$。 + Subtask9(25pts)：无特殊限制。