题目描述

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}$ 即被认为正确。

3 3
1 9
2 7
3 5
4 11
3 11
2 11

0.166666666666667
0.777777777777778
0.200000000000000

2 3
2 3
1 3
2 3
2 4
1 5

1.000000000000000
0.666666666666667
0.200000000000000

15 15
292779 375199
116635 225902
148578 226068
87307 451405
253236 726584
7605 375809
126859 270213
591988 654709
196632 352761
1773 222995
434502 573614
10721 102369
9513 26136
48256 550119
55076 105412
101605 809526
227659 911420
404295 854806
51424 889903
662575 874892
602228 826245
571439 915011
587102 963048
681507 927659
282201 890538
939465 950708
426980 913775
335175 864072
360417 839341
826102 957348

0.000012713265021
0.000042412418356
0.000005159760754
0.000056053811659
0.000000636912172
0.000007470291672
0.000002910589598
0.000029259443485
0.000001160644711
0.000003287646013
0.000000000000000
0.000004108497194
0.000003781447462
0.000002088009605
0.000000000000000

提示

样例 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)：无特殊限制。