#include <iostream>
#define int unsigned long long
#define bint __int128_t
using namespace std;

const int MAXN=3010;
bint MOD;

int lg[MAXN];
bool vst[MAXN];
int T,n;

void init_lg()
{
    int i=1,cnt=0;
    while(i<MAXN)
    {
        lg[i]=cnt;
        cnt++;i<<=1;
    }
    cnt=1;
    for(int i=3;i<MAXN;i++)
    {
        if(lg[i]==0)
            lg[i]=cnt;
        else
            cnt++;
    }
}

struct st
{
    int n;int dt[MAXN];
    int st[19][MAXN];
    void init()
    {
        for(int i=1;i<=n;i++)
            st[0][i]=dt[i];
        for(int i=1;(1<<i)<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                st[i][j]=st[i-1][j];
                if(j+(1<<(i-1))<=n )
                    st[i][j]=max(st[i][j],st[i-1][j+(1<<(i-1))]);
            }
        }
    }
}sa,sb;

int l[MAXN],r[MAXN];
bint sum[MAXN][MAXN];
void calc(int l)
{
    sum[l][l]=sa.dt[l]*sb.dt[l];
    for(int i=l+1;i<=n;i++)
    {
        sum[l][i]=sum[l][i-1];
        for(int ll=l;ll<=i;ll++)
        {
            int len=i-ll+1;
            int tt=lg[len];
            int ma=max(sa.st[tt][ll],sa.st[tt][i-(1<<tt)+1]);
            int mb=max(sb.st[tt][ll],sb.st[tt][i-(1<<tt)+1]);
            sum[l][i]+=ma*mb;
            sum[l][i]%=MOD;
        }
    }
}

signed main()
{
    freopen("match.in","r",stdin);
    freopen("match.out","w",stdout);
    int b=1;
    b<<=63;b-=1;b*=2;b+=1;
    MOD=b;
    MOD+=1;
    cin>>T>>n;
    sa.n=sb.n=n;
    for(int i=1;i<=n;i++)
        cin>>sa.dt[i];
    for(int j=1;j<=n;j++)
        cin>>sb.dt[j];
    sa.init();
    sb.init();
    init_lg();
    int Q;
    cin>>Q;
    for(int i=1;i<=Q;i++)
        cin>>l[i]>>r[i];
    /*
    for(int i=0;i<=3;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cout<<sa.st[i][j];
        }
        cout<<endl;
    }
    for(int i=0;i<=3;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cout<<sb.st[i][j];
        }
        cout<<endl;
    }*/
    for(int qq=1;qq<=Q;qq++)
    {
        if(!vst[l[qq]])
            calc(l[qq]),vst[l[qq]]=true;
        int ians=sum[l[qq]][r[qq]];
        cout<<ians<<endl;
        /*
        bint ans=0;
        for(int p=l[qq];p<=r[qq];p++)
            for(int q=p;q<=r[qq];q++)
            {
                int len=q-p+1;
                int tt=lg[len];
                int ma=max(sa.st[tt][p],sa.st[tt][q-(1<<tt)+1]);
                int mb=max(sb.st[tt][p],sb.st[tt][q-(1<<tt)+1]);
                ans+=ma*mb;
                ans%=MOD;
            }*/
    }
}//it's so difficult,I can't manage to solve it!8 point.
