Signal Tower

/*===============*\
|  ID: TMANDZU    |
|    LANG: C++    |
\*===============*/
//Tornike Mandzulashvili
//#pragma comment(linker,"/STACK:256000000")
#include <stdio.h>
#include <algorithm>
#include <iostream>

#define EPS 0.000000001
#define Pi 3.1415926535897932384626433832795028841971
#define hash1 1000003
#define hash2 1000033
#define md 1000000007
#define INF 1000000500
#define mp make_pair
#define pb push_back
#define S size()
#define MX(aa,bb) (aa>bb?aa:bb)
#define MN(aa,bb) (aa<bb?aa:bb)
#define fi first
#define se second
#define PI pair < int,int >
#define REP(i,a,n) for(i=a;i<n;i++)
#define sc scanf
#define pt printf
#define big long long
#define VI vector <int>
#define DID (long long)


using namespace std;

const int T=100005;

int L[T],R[T],A[T],B[T];
long long f[T],d[T];
int a,b,ll,rr,mid,i,N,Q;
long long x;
long long answer[T];
long long s[2][18][T],v[2][18][T];
PI I[T];

struct node
{
    int l,r;
    long long sum;
};

node g[2][4*T];

void build(int a,int b,int u,int deg,int n)
{
    g[n][u].l=a;g[n][u].r=b;

    if (a==b)
    {
        if (!n){
        g[n][u].sum=d[a];
        v[n][deg][a]=d[a];
        s[n][deg][a]=d[a];}else
        {
            v[n][deg][a]=I[a].se;
        }
        return;
    }

    int mid=(a+b)>>1;
    build(a,mid,2*u,deg+1,n);
    build(mid+1,b,2*u+1,deg+1,n);

    int ll=a,llend=mid;
    int rr=mid+1,rrend=b;

    for (int i=a;i<=b;i++)
    if (ll==llend+1) v[n][deg][i]=v[n][deg+1][rr++]; else
    if (rr==rrend+1) v[n][deg][i]=v[n][deg+1][ll++]; else
    if (v[n][deg+1][ll]<v[n][deg+1][rr]) v[n][deg][i]=v[n][deg+1][ll++]; else v[n][deg][i]=v[n][deg+1][rr++];

    s[n][deg][a]=v[n][deg][a];
    for (int i=a+1;i<=b;i++)
    s[n][deg][i]= DID s[n][deg][i-1]+v[n][deg][i];

    g[n][u].sum=s[n][deg][b];
}

int go(int u,int deg,int n)
{
    if (g[n][u].l>b || a>g[n][u].r) return 0;
    if (a<=g[n][u].l && g[n][u].r<=b) return g[n][u].r+1-(lower_bound(v[n][deg]+g[n][u].l,v[n][deg]+g[n][u].r+1,x)-v[n][deg]);
    return go(2*u,deg+1,n)+go(2*u+1,deg+1,n);
}

long long get(int u,int deg,int n)
{
    if (g[n][u].l>b || a>g[n][u].r) return 0;
    if (a<=g[n][u].l && g[n][u].r<=b) {
            int p=lower_bound(v[n][deg]+g[n][u].l,v[n][deg]+g[n][u].r+1,x)-v[n][deg];
            long long h=0;
            if (p>g[n][u].l)
            h+= DID (p-g[n][u].l)*x-s[n][deg][p-1];
            if (p>g[n][u].l)
            h+=DID ( DID g[n][u].sum-s[n][deg][p-1])- DID (g[n][u].r+1-p)*x; else
            h+=DID ( DID g[n][u].sum)- DID (g[n][u].r+1-p)*x;
            return h;
    }
    return DID get(2*u,deg+1,n)+get(2*u+1,deg+1,n);
}

bool check(int X)
{
    x=f[X];
    a=L[i];
    b=R[i];
    return (go(1,0,0)>=(R[i]-L[i]+2)/2);
}

int countt(int u,int deg,int n)
{
    int LL=g[n][u].l;
    int RR=g[n][u].r;

  //  cout<<"l da r "<<LL<<" "<<RR<<" "<<(upper_bound(v[n][deg]+LL,v[n][deg]+RR+1,b)-lower_bound(v[n][deg]+LL,v[n][deg]+RR+1,a))<<endl;

    return (upper_bound(v[n][deg]+LL,v[n][deg]+RR+1,b)-lower_bound(v[n][deg]+LL,v[n][deg]+RR+1,a));
}

int godown(int raod,int u,int deg,int n)
{
  //  cout<<u<<endl;
    if (g[n][u].l==g[n][u].r) return g[n][u].r;
    int h=countt(2*u,deg+1,n);

  //  cout<<raod<<" "<<u<<" "<<h<<endl;

    if (h>=raod) return godown(raod,2*u,deg+1,n);else return godown(raod-h,2*u+1,deg+1,n);
}

void solve()
{
    build(1,N,1,0,0);
    for (i=1;i<=N;i++)
    f[i]=d[i];
    sort(f+1,f+N+1);

    for (i=1;i<=N;i++)
    I[i]=mp(d[i],i);
    sort(I+1,I+N+1);

  //  cout<<"ARRAY "<<"\n";
  //  for (i=1;i<=N;i++)
 //   cout<<I[i].fi<<" ";
  //  cout<<endl;

    build(1,N,1,0,1);

  //  cout<<"% SHIA "<<g[1][5].l<<" "<<g[1][5].r<<endl;

    for (i=1;i<=Q;i++)
    {
        a=L[i];
        b=R[i];

        ll=godown((b-a+2)/2,1,0,1);
        x=I[ll].fi;

   //     cout<<"---"<<a<<" "<<b<<" "<<ll<<" "<<x<<endl;

        answer[i]+=get(1,0,0);
    }
}

main()
{
   // freopen("text.in","r",stdin);   freopen("text.out","w",stdout);

    scanf("%d %d",&N,&Q);
    for (i=1;i<=N;i++)
    scanf("%d",A+i);
    for (i=1;i<=N;i++)
    scanf("%d",B+i);
    for (i=1;i<=Q;i++)
    scanf("%d %d",L+i,R+i);

    for (i=1;i<=N;i++)
    d[i]=DID A[i]+B[i];

    solve();

    for (i=1;i<=N;i++)
    d[i]=DID A[i]-B[i];

    solve();

    for (i=1;i<=Q;i++)
    if (answer[i]%2) printf("%lld.50000\n",answer[i]/2);else
    printf("%lld.0000\n",answer[i]/2);

}