#include <bits/stdc++.h>
using namespace std;
long long per[1000010];
long long tab[1000010];
long long pos[1000010];
long long nas[20][1000010];
long long wy[1000010];
void policz(long long gdzie) {
  for (long long i = 1; i < 20; i++) {
    nas[i][gdzie] = nas[i - 1][nas[i - 1][gdzie]];
  }
}
long long n;
long long skocz(long long gdzie) {
  long long ile = n - 1;
  for (long long i = 19; i >= 0; i--) {
    if ((1 << i) <= ile) {
      gdzie = nas[i][gdzie];
      ile -= (1 << i);
    }
  }
  if (gdzie == 0) return 1000000000000000000ll;
  return gdzie;
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  long long m, q;
  cin >> n >> m >> q;
  for (long long a, i = 1; i <= n; i++) {
    cin >> a;
    per[a] = i;
  }
  for (long long i = 1; i <= m; i++) {
    cin >> tab[i];
    tab[i] = per[tab[i]] - 1;
  }
  for (long long i = m; i > 0; i--) {
    nas[0][i] = pos[(tab[i] + 1) % n];
    pos[tab[i]] = i;
    policz(i);
    wy[i] = skocz(i);
  }
  for (long long i = m - 1; i > 0; i--) {
    wy[i] = min(wy[i], wy[i + 1]);
  }
  while (q--) {
    long long l, r;
    cin >> l >> r;
    if (wy[l] <= r)
      cout << 1;
    else
      cout << 0;
  }
  return 0;
}
