#include<cstdio>
#include<algorithm>
int T,n,q;
int a[250086],b[250086];
struct ask{
	int l,r,no;
	bool operator < (const ask& rhs)const
	{return r<rhs.r;} 
}asks[250086];
unsigned long long res[250086];
struct node{
	int l,r;
	unsigned long long f,mx_t,mx_a,mx_b;
	int lzd_f,lzd_mx_a,lzd_mx_b;
}tr[1000086];
inline void push_up(int now)
{
    tr[now].f=tr[now<<1].f+tr[now<<1|1].f;
    tr[now].mx_t=tr[now<<1].mx_t+tr[now<<1|1].mx_t;
    tr[now].mx_a=tr[now<<1].mx_a+tr[now<<1|1].mx_a;
    tr[now].mx_b=tr[now<<1].mx_b+tr[now<<1|1].mx_b;
}
inline void run_tag_f(int now,int val)
{
	tr[now].f+=val*tr[now].mx_t;
	tr[now].lzd_f+=val;
}
inline void down_f(int now)
{
	if(tr[now].lzd_f)
    {
        run_tag_f(now<<1,tr[now].lzd_f);
        run_tag_f(now<<1,tr[now].lzd_f);
        tr[now].lzd_f=0;
    }
}
inline void run_tag_a(int now,int val)
{
	if(tr[now].l!=tr[now].r) down_f(now);
    tr[now].mx_t=tr[now].mx_b*val;
    tr[now].lzd_mx_a=val;tr[now].mx_a=1ull*val*(tr[now].r-tr[now].l+1);
}
inline void run_tag_b(int now,int val)
{
	if(tr[now].l!=tr[now].r) down_f(now);
    tr[now].mx_t=tr[now].mx_a*val;
    tr[now].lzd_mx_b=val;tr[now].mx_b=1ull*val*(tr[now].r-tr[now].l+1);
}
inline void lzd_down(int now)
{
    if(tr[now].lzd_mx_a!=-1)
    {
        run_tag_a(now<<1,tr[now].lzd_mx_a);
        run_tag_a(now<<1|1,tr[now].lzd_mx_a);
        tr[now].lzd_mx_a=-1;
    }
    if(tr[now].lzd_mx_b!=-1)
    {
        run_tag_b(now<<1,tr[now].lzd_mx_b);
        run_tag_b(now<<1|1,tr[now].lzd_mx_b);
        tr[now].lzd_mx_b=-1;
    }
    down_f(now);
}
void build(int now,int l,int r)
{
    tr[now].l=l,tr[now].r=r;
    tr[now].lzd_mx_a=tr[now].lzd_mx_b=-1;
    if(l!=r)
    {
        int mid=(l+r)>>1;
        build(now<<1,l,mid);
        build(now<<1|1,mid+1,r);
    }
}
void cast_a(int now,int l,int r,int val)
{
    if(l<=tr[now].l&&tr[now].r<=r)
        return run_tag_a(now,val),void();
    lzd_down(now);
    int mid=(tr[now].l+tr[now].r)>>1;
    if(l<=mid) cast_a(now<<1,l,r,val);
    if(mid<r) cast_a(now<<1|1,l,r,val);
    push_up(now);
}
void cast_b(int now,int l,int r,int val)
{
    if(l<=tr[now].l&&tr[now].r<=r)
        return run_tag_b(now,val),void();
    lzd_down(now);
    int mid=(tr[now].l+tr[now].r)>>1;
    if(l<=mid) cast_b(now<<1,l,r,val);
    if(mid<r) cast_b(now<<1|1,l,r,val);
    push_up(now);
}
void add(int now,int l,int r,int val)
{
    if(l<=tr[now].l&&tr[now].r<=r)
        return run_tag_f(now,val),void();
    lzd_down(now);
    int mid=(tr[now].l+tr[now].r)>>1;
    if(l<=mid) add(now<<1,l,r,val);
    if(mid<r) add(now<<1|1,l,r,val);
    push_up(now);
}
unsigned long long query(int now,int l,int r)
{
    if(l<=tr[now].l&&tr[now].r<=r)
        return tr[now].f;
    lzd_down(now);
    int mid=(tr[now].l+tr[now].r)>>1;
    if(r<=mid) return query(now<<1,l,r);
    else if(mid<l) return query(now<<1|1,l,r);
    else return query(now<<1,l,r)+query(now<<1|1,l,r);
}
int pos_a[250086],pos_b[250086];
namespace mx_tree{
    struct node{
        int l,r,mn;
    }tr[1000086];
    void build(int now,int l,int r)
    {
        tr[now].l=l;tr[now].r=r;
        tr[now].mn=0;
        if(l!=r)
        {
            int mid=(l+r)>>1;
            build(now<<1,l,mid);
            build(now<<1|1,mid+1,r);
        }
    }
    void change(int now,int pos,int val)
    {
        if(tr[now].l==tr[now].r) return tr[now].mn=val,void();
        int mid=(tr[now].l+tr[now].r)>>1;
        if(pos<=mid) change(now<<1,pos,val);
        else change(now<<1|1,pos,val);
        tr[now].mn=std::max(tr[now<<1].mn,tr[now<<1|1].mn);
    }
    int query(int now,int l,int r)
    {
        if(l>r) return 0;
        if(l<=tr[now].l&&tr[now].r<=r)
            return tr[now].mn;
        int mid=(tr[now].l+tr[now].r)>>1;
        if(r<=mid) return query(now<<1,l,r);
        else if(mid<l) return query(now<<1|1,l,r);
        else return std::max(query(now<<1,l,r),query(now<<1|1,l,r));
    }
}
int main()
{
    freopen("match2.in","r",stdin);
    freopen("P8868.out","w",stdout);
	scanf("%d%d",&T,&n);
	for(int i=1;i<=n;i++) scanf("%d",a+i);
    mx_tree::build(1,1,n);
    for(int i=1;i<=n;i++)
    {
        pos_a[i]=mx_tree::query(1,a[i]+1,n)+1;
        mx_tree::change(1,a[i],i);
    }
	for(int i=1;i<=n;i++) scanf("%d",b+i);
	mx_tree::build(1,1,n);
    for(int i=1;i<=n;i++)
    {
        pos_b[i]=mx_tree::query(1,b[i]+1,n)+1;
        mx_tree::change(1,b[i],i);
    }
	scanf("%d",&q);
	for(int i=1;i<=q;i++) scanf("%d%d",&asks[i].l,&asks[i].r),asks[i].no=i;
	std::sort(asks+1,asks+1+q);
    build(1,1,n);
    for(int i=1,j=0;i<=q;i++)
    {
        while(j<asks[i].r)
        {
            j++;cast_a(1,pos_a[j],j,a[j]);
            cast_b(1,pos_b[j],j,b[j]);
            add(1,1,j,1);
        }
        res[asks[i].no]=query(1,asks[i].l,asks[i].r);
    }
	for(int i=1;i<=q;i++) printf("%llu\n",res[i]);
	return 0;
}