#include<bits/stdc++.h>
#define F(i, x, y) for (int (i) = (x);(i) <= (y);(i)++)
using namespace std;

const int N = 5e5 + 5;
int n, q, a[N], c[N], lp[N];
stack<int> lb[N];
namespace st {
	int root[N];
	int sum[40 * N], ls[40 * N], rs[40 * N], cnt;
	int build (int l, int r) {
		int p = ++cnt;
		if (l != r) {
			int mid = (l + r) >> 1;
			ls[p] = build (l, mid);
			rs[p] = build (mid + 1, r); 
		}
		return p;
	}
	int modify (int p, int l, int r, int k) {
		int np = ++cnt;
		ls[np] = ls[p]; rs[np] = rs[p];
		sum[np] = sum[p];
		if (l == r) sum[np]++;
		else {
			int mid = (l + r) >> 1;
			if (k <= mid) ls[np] = modify (ls[p], l, mid, k);
			else rs[np] = modify (rs[p], mid + 1, r, k);
			sum[np] = sum[ls[np]] + sum[rs[np]];
		}
		return np;
	}
	int query (int p, int tl, int tr, int ql, int qr) {
		if (ql <= tl && tr <= qr) return sum[p];
		else {
			int mid = (tl + tr) >> 1;
			int ans = 0;
			if (ql <= mid) ans += query (ls[p], tl, mid, ql, qr);
			if (qr > mid) ans += query (rs[p], mid + 1, tr, ql, qr);
			return ans;
		}
	}
}
int main () {
	ios::sync_with_stdio (false);
	cin.tie (0);
	cin >> n >> q;
	F (i, 1, n) cin >> a[i];
	F (i, 1, n) cin >> c[i];
	F (i, 1, n) {
		if (a[i] == 0) lb[c[i]].push (i);
		else {
			if (lb[c[i]].size ()) {
				lp[i] = lb[c[i]].top ();
				lb[c[i]].pop ();
			}
		}
	}
	st::root[0] = st::build (0, n);
	F (i, 1, n) {
		st::root[i] = st::modify (st::root[i - 1], 0, n, lp[i]);
	}
	int l, r;
	F (i, 1, q) {
		cin >> l >> r;
		cout << st::query (st::root[r], 1, n, l, r) - st::query (st::root[l - 1], 1, n, l, r) << "\n";
	} 
	return 0; 
}