#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int maxn=250005;
const int maxq=250005;
struct QuerY
{
    int l,r,id;
    inline bool operator <(const QuerY &q) const
    {
        return r<q.r;
    }
}qs[maxq];
int n,q,a[maxn],b[maxn],sta[2][maxn],top[2],L[maxn],R[maxn];
ull ans[maxq],tr[maxn],tr1[maxn];
inline void update(ull *tr,int x,ull z) { for(;x<=n;x+=x&-x) tr[x]+=z; }
inline ull query(ull *tr,int x) { ull res=0; for(;x;x&=x-1) res+=tr[x]; return res;}
int main()
{
    int i,j,x,y,L,R;
    ull val;
    freopen("match.in","r",stdin),freopen("match.out","w",stdout);
    scanf("%*d%d",&n);
    for(i=1;i<=n;i++) scanf("%d",&a[i]);
    for(i=1;i<=n;i++) scanf("%d",&b[i]);
    scanf("%d",&q);
    for(i=0;i<q;i++) scanf("%d%d",&qs[i].l,&qs[i].r),qs[i].id=i;
#ifdef DEBUG
    if(0)
#else
    if(n<=30 && q<=30)
#endif
    {
        for(i=0;i<q;i++)
        {
            ans[i]=0;
            for(x=qs[i].l;x<=qs[i].r;x++)
            {
                L=R=0;
                for(y=x;y<=qs[i].r;y++)
                    L=max(L,a[y]),R=max(R,b[y]),ans[i]+=L*R;
            }
        }
    }
    else
    {
        sort(qs,qs+q);
        for(i=1;i<=n;i++) tr[i]=tr1[i]=0;
        for(i=1,j=0,top[0]=top[1]=0,sta[0][0]=sta[1][0]=0;i<=n;i++)
        {
            while(top[0] && a[sta[0][top[0]]]<a[i]) top[0]--;
            sta[0][++top[0]]=i;
            while(top[1] && b[sta[1][top[1]]]<b[i]) top[1]--;
            sta[1][++top[1]]=i;
            // printf("%d\n",i);
            for(x=top[0]-1,y=top[1]-1,R=i;x>=0 || y>=0;R=L-1)
            {
                val=(ull)a[sta[0][x+1]]*(ull)b[sta[1][y+1]];
                if(sta[0][x]<sta[1][y]) L=sta[1][y--]+1;
                else if(sta[0][x]>sta[1][y]) L=sta[0][x--]+1;
                else L=sta[0][x--]+1,y--;
                update(tr,L,(ull)(R+1)*val),update(tr1,L,-val),
                update(tr,R+1,-(ull)(R+1)*val),update(tr1,R+1,val),
                update(tr,1,(ull)(R-L+1)*val),update(tr,L,-(ull)(R-L+1)*val);
                // printf("%d %d %llu\n",L,R,val);
            }
            for(;j<q && qs[j].r==i;j++) ans[qs[j].id]=query(tr,qs[j].l)+query(tr1,qs[j].l)*(ull)qs[j].l;
        }
    }
    for(i=0;i<q;i++) printf("%llu\n",ans[i]);
    fclose(stdin),fclose(stdout);
    return 0;
}