#include<bits/stdc++.h>
#define fi first
#define se second
#define mk make_pair
#define pb push_back
#define pii pair<int,int>
#define ull unsigned long long
#define int long long
using namespace std;
const int N=2e5+100;
int n,m,q;
int a[N],b[N];
int st1[N][20],st2[N][20];
int q1(int l,int r)
{
	int k=log2(r-l+1);
	return max(st1[l][k],st1[r-(1<<k)+1][k]);
}
int q2(int l,int r)
{
	int k=log2(r-l+1);
	return max(st2[l][k],st2[r-(1<<k)+1][k]);
}
signed main()
{
    freopen("match.in","r",stdin);
    freopen("match.out","w",stdout);
    int _;scanf("%lld%lld",&_,&n);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]),st1[i][0]=a[i];
    for(int i=1;i<=n;i++)scanf("%lld",&b[i]),st2[i][0]=b[i];
    for(int i=1;i<=20;i++)
    	for(int j=1;j+(1<<i)-1<=n;j++)
    		st1[j][i]=max(st1[j][i-1],st1[j+(1<<i-1)][i-1]),
    		st2[j][i]=max(st2[j][i-1],st2[j+(1<<i-1)][i-1]);
    int Q;scanf("%lld",&Q);
    a[0]=b[0]=1e9;
    if(n<=3000)
    {
	    while(Q--)
	    {
	        int l,r;scanf("%lld%lld",&l,&r);
	        ull ans=0;
	        vector<int>s1,s2;
	        s1.push_back(0);s2.push_back(0);
	        	for(int p=l;p<=r;p++)
	        		for(int q=p;q<=r;q++)
	        			ans=ans+q1(p,q)*q2(p,q);
	        printf("%llu\n",ans);
	    }
	    return 0;
	}
	while(Q--)
    {
        int l,r;scanf("%lld%lld",&l,&r);
        ull ans=0;
        vector<int>s1,s2;
        s1.push_back(0);s2.push_back(0);
        for(int i=l;i<=r;i++)
        {
            while(!s1.empty()&&s1.back()<a[i])s1.pop_back();
            while(!s2.empty()&&s2.back()<b[i])s2.pop_back();
            s1.push_back(i);s2.push_back(i);
            vector<pii>s3;
            for(auto y:s1)s3.push_back(mk(y,1));
            for(auto y:s2)s3.push_back(mk(y,2));
            sort(s3.begin(),s3.end());
            int v1=0,v2=b[i];
            for(int j=s3.size()-2;j>=0;j--)
            {
            	int t1=s3[j].se,t2=s3[j+1].se;
            	if(s3[j].se==0)break;
            	if(s3[j].fi==s3[j+1].fi)ans=ans+a[s3[j].fi]*b[s3[j].fi];
            	else 
            	if(t1==t2)
            	{
            		if(t1==1)ans=ans+v2*a[s3[j+1].fi]*(s3[j+1].fi-s3[j].fi);
            		else ans=ans+v1*b[s3[j+1].fi]*(s3[j+1].fi-s3[j].fi);
				}
				else 
				{
					if(t2==1)ans=ans+v2*a[s3[j+1].fi]*(s3[j+1].fi-s3[j].fi);
					else ans=ans+v1*b[s3[j+1].fi]*(s3[j+1].fi-s3[j].fi);
				}
				if(t1==1)v1=a[s3[j].fi];
				else v2=b[s3[j].fi];
			}
        }
        printf("%llu\n",ans);
    }
    return 0;
}