#include <stdio.h>
#include <algorithm>
#include <set>
#include <string.h>
#include <deque>
#include <vector>
#define int unsigned long long
int read()
{
    int x=0,f=1,c=getchar();
    while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
    while(c>47&&c<58)x=x*10+c-48,c=getchar();
    return x*f;
}
int re1d()
{
    int c=getchar();
    while(c<48||c>57)c=getchar();
    return c-48;
}
int a[1000005],b[1000005];
int na[1000005],nb[1000005];
int mxa[3005][3005],mxb[3005][3005];
int sa[3005][3005];
int pa[1000005],pb[1000005];
const int B=300;
struct Mo{
    int l,r,lb,id;
    bool operator<(const Mo&b)const{
        return lb==b.lb?r<b.r:lb<b.lb;
    }
}f[1000005];
int ns[1000005];
int ans;
void expandr(int r,int l,int v)
{
    int A=a[r],B=b[r];
    for(int x=r;x>=l;)
    {
        int t=std::max(l,std::max(pa[x]+1,pb[x]+1));
        ans+=(x-t+1)*A*B*v;
        x=t-1;
        A=std::max(A,a[x]);
        B=std::max(B,b[x]);
    }
}
void expandl(int l,int r,int v)
{
    int A=a[l],B=b[l];
    for(int x=l;x<=r;)
    {
        int t=std::min(r,std::min(na[x]-1,nb[x]-1));
        ans+=(t-x+1)*A*B*v;
        x=t+1;
        A=std::max(A,a[x]);
        B=std::max(B,b[x]);
    }
}
signed main()
{
    freopen("match.in","r",stdin);
    freopen("match.out","w",stdout);
    int T=read(),n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=n;i++)b[i]=read();;
    int q=read();
    if(n<=3000&&q<=3000)
    {
        for(int i=1;i<=n;i++)
        {
            mxa[i][i]=a[i];mxb[i][i]=b[i];
            sa[i][i]=a[i]*b[i];
            for(int j=i+1;j<=n;j++)
                mxa[i][j]=std::max(mxa[i][j-1],a[j]),
                mxb[i][j]=std::max(mxb[i][j-1],b[j]);
        }
        for(int l=2;l<=n;l++)
            for(int i=1,j=l;j<=n;i++,j++)
                sa[i][j]=mxa[i][j]*mxb[i][j]+sa[i+1][j]+sa[i][j-1]-sa[i+1][j-1];
        while(q--)
        {
            int l=read(),r=read();
            printf("%llu\n",sa[l][r]);
        }
        return 0;
    }
    std::set<std::pair<int,int> >s;
    for(int i=1;i<=n;i++)
    {
        for(std::set<std::pair<int,int> >::iterator g=s.begin();g!=s.end();g=s.begin())
            if(g->first<a[i])
            {
                na[g->second]=i;
                s.erase(g);
            }else break;
        s.insert(std::make_pair(a[i],i));
    }for(int i=1;i<=n;i++)if(na[i]==0)na[i]=n+1;s.clear();
    for(int i=1;i<=n;i++)
    {
        for(std::set<std::pair<int,int> >::iterator g=s.begin();g!=s.end();g=s.begin())
            if(g->first<b[i])
            {
                nb[g->second]=i;
                s.erase(g);
            }else break;
        s.insert(std::make_pair(b[i],i));
    }for(int i=1;i<=n;i++)if(nb[i]==0)nb[i]=n+1;s.clear();
    for(int i=n;i>=1;i--)
    {
        for(std::set<std::pair<int,int> >::iterator g=s.begin();g!=s.end();g=s.begin())
            if(g->first<a[i])
            {
                pa[g->second]=i;
                s.erase(g);
            }else break;
        s.insert(std::make_pair(a[i],i));
    }for(int i=1;i<=n;i++)if(na[i]==0)na[i]=n+1;s.clear();
    for(int i=n;i>=1;i--)
    {
        for(std::set<std::pair<int,int> >::iterator g=s.begin();g!=s.end();g=s.begin())
            if(g->first<b[i])
            {
                pb[g->second]=i;
                s.erase(g);
            }else break;
        s.insert(std::make_pair(b[i],i));
    }for(int i=1;i<=n;i++)if(nb[i]==0)nb[i]=n+1;s.clear();
    // for(int i=1;i<=n;i++)printf("%llu ",na[i]);puts("");
    // for(int i=1;i<=n;i++)printf("%llu ",nb[i]);puts("");
    if(1<=T&&T<=13)
    {
        while(q--)
        {
            int l=read(),r=read(),ans=0;
            for(int i=l;i<=r;i++)
            {
                int A=a[i],B=b[i];
                for(int x=i;x<=r;)
                {
                    int t=std::min(r,std::min(na[x]-1,nb[x]-1));
                    ans+=(t-x+1)*A*B;
                    x=t+1;
                    A=std::max(A,a[x]);
                    B=std::max(B,b[x]);
                }
            }
            printf("%llu\n",ans);
        }
        return 0;
    }
    // q=5;
    for(int i=1;i<=q;i++)
    {
        f[i].l=read(),f[i].r=read();f[i].lb=f[i].l/B;f[i].id=i;
    }
    std::sort(f+1,f+1+q);
    int l=1,r=0;
    for(int i=1;i<=q;i++)
    {
        int L=f[i].l,R=f[i].r;
        while(r<R)expandr(++r,l,1);
        while(l>L)expandl(--l,r,1);
        while(r>R)expandr(r--,l,-1);
        while(l<L)expandl(l++,r,-1);
        ns[f[i].id]=ans;
    }
    for(int i=1;i<=q;i++)printf("%llu\n",ns[i]);
}