#include<bits/stdc++.h>
using namespace std;
#define sf(x) scanf("%lld",&x)
#define sff(x,y) scanf("%lld%lld",&x,&y)
#define endl '\n'
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pf(x) printf("%lld",x)
#define pii pair<int,int> 
//#define f first 
#define s second
#define int long long



//
const int N = 5e5+10;
int f[N],tr[N],a[N],b[N];
int m,n;
stack<int>st[N];

//

int lowbit(int x)
{
    return x & -x;
}
void add(int x, int k)
{
    for (int i = x; i <= m; i += lowbit(i))tr[i] += k;
}
int ask(int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i))res += tr[i];
    return res;
}
pii q[N];
vector<int> ve[N];
map<pii,int> res;
//


void solve()
{
    cin>>m>>n;
    
    for(int i=1;i<=m;i++) cin>>a[i];
    for(int i=1;i<=m;i++) cin>>b[i];
    
    for(int i=1;i<=n;i++)
    {
        int l,r;
        cin>>l>>r;
        q[i]={l,r};
        ve[r].push_back(l);
    }
    
    for(int i=1;i<=m;i++)
    {
        if(a[i]==0) st[b[i]].push(i),f[i]=f[i-1];
        else 
        {
            if(st[b[i]].size()) {
                int t = st[b[i]].top();
                add(t+1,1);
                add(i,-1);
                f[i]=f[i-1]+1;
                st[b[i]].pop();
            }
            else f[i]=f[i-1];
        }
        for(auto j:ve[i])
            res[{j,i}]=f[i]-f[j]-ask(j);
    }
    for(int i=1;i<=n;i++) cout<<res[q[i]]<<endl;
}
signed main()
{
    IOS;
    int _=1;
    while(_--)
        solve();
    return 0;
}