#include<bits/stdc++.h>
#define int long long
#define rd(x) x=read()
using namespace std;
const int mod=1e9+7;
const int N=3005;
int ksm(int x,int y)
{
    int ans=1;
    while (y)
    {
        if (y%2==1) ans=ans*x%mod;
        y/=2;x=x*x%mod;
    }
    return ans;
}
int read()
{
    int x=0,f=1;char c=getchar();
    while (c>'9' || c<'0') {if (c=='-') f=-1;c=getchar();}
    while ('0'<=c && c<='9') {x=x*10+c-'0';c=getchar();}
    return x*f;
}

int T,n;
unsigned long long M[N][N],S[N][N],mx[N][N];
int a[N],b[N],pa[N],pb[N];
int la[N],ra[N],lb[N],rb[N];
unsigned long long cal(int l,int r,int m)
{
    unsigned long long ret=0;
    //printf("cal(%lld,%lld,%lld)=",l,r,m);
    for (int i=l;i<=m;i++) for (int j=m;j<=r;j++) ret+=mx[i][j];
    //cout<<ret<<"\n";
    return ret;
    return (M[m][r]-M[m][m-1])-(M[l-1][r]-M[l-1][r-1]);
}
signed main()
{
    srand(time(NULL));
    freopen("match.in","r",stdin);
    freopen("match.out","w",stdout);
    rd(T);rd(n);
    for (int i=1;i<=n;i++) rd(a[i]),pa[a[i]]=i;
    for (int i=1;i<=n;i++) rd(b[i]),pb[a[i]]=i;
    for (int i=1;i<=n;i++) la[i]=ra[i]=lb[i]=rb[i]=i;
    for (int i=1;i<=n;i++)
    {
        for (int j=i+1;j<=n;j++) if (a[j]<a[i]) ra[i]=j;else break;
        for (int j=i+1;j<=n;j++) if (b[j]<b[i]) rb[i]=j;else break;
        for (int j=i-1;j>=1;j--) if (a[j]<a[i]) la[i]=j;else break;
        for (int j=i-1;j>=1;j--) if (b[j]<b[i]) lb[i]=j;else break;
    }
    for (int i=1;i<=n;i++)
    {
        int Max=0;
        for (int j=i;j<=n;j++)
        {
            Max=max(a[j],Max);mx[i][j]=Max;
            //printf("max(%lld,%lld)=%lld\n",i,j,Max);
            //S[i][j]=S[i][j-1]+Max;
        }
    }
    
    for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) S[i][j]=S[i][j-1]+mx[i][j];
    for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) M[i][j]=M[i-1][j]+S[i][j];
    int Q;rd(Q);
    unsigned long long ans;
    while (Q--)
    {
        ans=0;
        int l,r;rd(l);rd(r);
        for (int i=l;i<=r;i++)
        {
            int L=lb[i],R=rb[i];
            unsigned long long B=b[i];
            ans+=cal(max(L,l),min(R,r),i)*B;
        }
        cout<<ans<<"\n";
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}
//