#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> mp;
int res[N];
//


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;
		ve[r].push_back(l);
		mp[{l,r}]=i;
	}
	
	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()) continue;
			int t = st[b[i]].top();
			add(t+1,1);
			add(i,-1);
			f[i]=f[i-1]+1;
			st[b[i]].pop();
		}
		
		for(auto j:ve[i])
			res[mp[{j,i}]]=f[i]-f[j]-ask(j);
	}
	
	for(int i=1;i<=n;i++) cout<<res[i]<<endl;
}
signed main()
{
	IOS;
	int _=1;
	while(_--)
		solve();
	return 0;
}