#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=25e4,N_=3005;
int a[N],b[N],mx_a[N_][N_],mx_b[N_][N_],T,n;
ull Mx[N_][N_],s[N_][N_],ANS[N_][N_];
void slv20()
{
	for(int i=1;i<=n;i++)
	{
		mx_a[i][i]=a[i];
		mx_b[i][i]=b[i];
		for(int j=i+1;j<=n;j++)
		{
			mx_a[i][j]=max(mx_a[i][j-1],a[j]);
			mx_b[i][j]=max(mx_b[i][j-1],b[j]);
		}
	}
	for(int i=1;i<=n;i++)
	{
		Mx[i][i]=s[i][i]=1ull*a[i]*b[i];
		for(int j=i+1;j<=n;j++)
		{
			Mx[i][j]=1ull*mx_a[i][j]*mx_b[i][j];
			s[i][j]=s[i][j-1]+Mx[i][j];
		}
	}
	for(int i=n;i;i--)
	{
		ANS[i][i]=Mx[i][i];
		for(int j=i+1;j<=n;j++)
		{
			ANS[i][j]=ANS[i+1][j]+s[i][j];
		}
	}
	int Q;
	scanf("%d",&Q);
	while(Q--)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		printf("%llu\n",ANS[l][r]);
	}
}
void slv()
{
	scanf("%d%d",&T,&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&b[i]);
	}
	if(n<=3000)
	{
		slv20();
		return ;
	}
}
int main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	slv();
	fclose(stdin);
	fclose(stdout);
	return 0;
}
