#include <bits/stdc++.h>
using namespace std;
const long long INF = 0x7f7f7f7f7f;
const long long mod=2305843009213693952;
int T, n;
int a[300000];
int b[300000];
inline int solve(int x,int y)
{
    int ans=0;
    for(int i=x;i<=y;i++)
    {
        for(int j=x;j<=y;j++)
        {
            ans+=(a[i]%mod*b[i]%mod)%mod;
            ans%=mod;
        }
    } 
    return ans;
}
int main()
{
    freopen("match.in","r",stdin);
    freopen("match.out","w",stdout);
    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]);
    }
    int q;
    scanf("%d",&q);
    for(int i=0;i<q;i++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d\n",solve(l,r));
    }
}