#3415. 世博会

世博会

Description

四年一度的世博会又要举办了,Q国很荣幸成为了这次世博会的主办方。Q国主席QQ从全国各地收集了N件物品排成

一排,作为Q国馆的展出物。对于相邻摆放的一些物品,如果过于相似会让人觉得无聊,如果差别过大又会让人觉

得突兀。为了让人们对这次世博会的展出满意,QQ需要知道一些相邻物品的“差异度”。为了方便表示,QQ给每个

物品都定义了两个属性值A、B,两件物品之间的“绝对差异值”定义为它们对应属性的差的绝对值较大的一个。对

于一些物品的“差异度”,类似求方差的方法,QQ总会首先设想一个理想的“平均物品”,它的两个属性可以为任

意实数,且它与这些物品中的每个物品的“绝对差异值”之和最小。而这些物品的“差异度”就定义为这个最小的

和。QQ每次会询问:从第Li个到第Ri个物品的“差异度”是多少。现在,这个任务交给了神犇你。

Format

Input

第一行两个整数N和Q,表示物品数和QQ的询问数。第二行N个整数A1到An,表示每个物品的A属性。第三行N个整数B

1到Bn,表示每个物品的B属性。之后Q行每行两个整数Li Ri,表示QQ的询问。

1<=N<=100000, 1<=Q<=100000, |Ai|,|Bi|<=1000000000,1<=Li<=Ri<=N

Output

共Q行,每行输出一个数,表示该次询问的物品的差异度,结果保留到小数点后两位。

Samples

4 2
1 6 -3 2
2 7 -1 3
1 4
2 3
10.00
9.00

Limitation

样例说明 对于第一个询问,平均物品的两个属性可以是1和2差异度为max(0,0)+max(5,5)+max(4,3)+max(1,1)=10对于第二个 询问,平均物品的两个属性可以是6和7差异度为max(0,0)+max(9,8)=9