#include<bits/stdc++.h>
using namespace std;

inline int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9')
	{
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x * f;
}

int T, n, q, bl, cnt;

unsigned long long ans;

int fa[505], fb[505], num[250005], a[250005], b[250005];

map<pair<int, int>, long long> A, B;

int aska(int p, int q)
{
	int Max = 0;	
	for(int i = p; i <= min(num[p] * bl, q); ++ i ) Max = max(Max, a[i]);
	for(int i = num[p] + 1; i <= num[q] - 1; ++ i ) Max = max(Max, fa[i]);
	for(int i = max(p, (num[q] - 1) * bl + 1); i <= q; ++ i ) Max = max(Max, a[i]);
	return Max;
}

int askb(int p, int q)
{
	int Max = 0;
	for(int i = p; i <= min(num[p] * bl, q); ++ i ) Max = max(Max, b[i]);
	for(int i = num[p] + 1; i <= num[q] - 1; ++ i ) Max = max(Max, fb[i]);
	for(int i = max(p, (num[q] - 1) * bl + 1); i <= q; ++ i ) Max = max(Max, b[i]);
	return Max;
}

signed main()
{
	freopen("match.in", "r", stdin);
	freopen("match.out", "w", stdout);
	T = read(), n = read();
	for(int i = 1; i <= n; ++ i ) a[i] = read();
	for(int i = 1; i <= n; ++ i ) b[i] = read();
	bl = floor(sqrt(n));
	cnt = n / bl;
	for(int i = 1; i <= n; ++ i ) 
	{
		num[i] = (i - 1) / bl + 1;
		fa[num[i]] = max(fa[num[i]], a[i]);
		fb[num[i]] = max(fb[num[i]], b[i]);
	}
	if(n % bl != 0) ++ cnt;
	for(int i = 1; i <= n; ++ i ) 
	  for(int j = 1; j <= n; ++ j )
	  {
	  	  A[make_pair(i, j)] = aska(i, j);
	  	  B[make_pair(i, j)] = askb(i, j);
	  }
	    
	q = read();
	while(q --)
	{
		int l = read(), r = read();
		ans = 0;
		for(int i = l; i <= r; ++ i )
		  for(int j = i; j <= r; ++ j )
		  {
		  	long long aa = A[make_pair(i, j)], bb = B[make_pair(i, j)];
		  	unsigned long long s = aa * bb % 18446744073709551615;
		  	ans = (ans + s) % 18446744073709551615;
		  }
		cout << ans << endl; 
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}
//ZJ-428 is so pretty!!!!! Lose my heart in! Love you!!(joke)
//2^64=18446744073709551616 Wrong!!!!!! WARNING but i can't change(__int128)