#include <bits/stdc++.h>
using namespace std;
int n, m, q;
int dp[1000005], nr[1000005], last[1000005], rez, prevv[17][200005];
int a[1000005], perm[1000005], poz[1000005], arb[1000005];
void insert(int now, int st, int dr, int poz, int val) {
  int mij = (st + dr) / 2;
  if (st == dr) {
    arb[now] = val;
    return;
  }
  if (poz <= mij)
    insert(now * 2, st, mij, poz, val);
  else
    insert(now * 2 + 1, mij + 1, dr, poz, val);
  arb[now] = max(arb[now * 2], arb[now * 2 + 1]);
}
void query(int now, int st, int dr, int le, int ri) {
  int mij = (st + dr) / 2;
  if (le > dr || ri < st) return;
  if (le <= st && dr <= ri)
    rez = max(rez, arb[now]);
  else {
    query(now * 2, st, mij, le, ri);
    query(now * 2 + 1, mij + 1, dr, le, ri);
  }
}
int anterior(int poz, int mutari) {
  int rez = poz;
  for (int i = 0; i < 17; i++)
    if ((1 << i) & mutari) rez = prevv[i][rez];
  return rez;
}
int main() {
  ios_base::sync_with_stdio(false), cin.tie(NULL);
  string s;
  cin >> n >> m >> q;
  for (int i = 1; i <= n; i++) cin >> perm[i], poz[perm[i]] = i;
  perm[0] = perm[n];
  for (int i = 1; i <= m; i++) {
    cin >> a[i];
    int b = poz[a[i]];
    b = last[perm[b - 1]];
    if (b) {
      prevv[0][i] = b;
      nr[i] = nr[b] + 1;
    } else {
      nr[i] = 1;
    }
    last[a[i]] = i;
  }
  for (int i = 1; i < 17; i++)
    for (int j = 1; j <= m; j++) prevv[i][j] = prevv[i - 1][prevv[i - 1][j]];
  for (int i = 1; i <= m; i++) {
    if (nr[i] >= n) dp[i] = anterior(i, n - 1), insert(1, 1, m, i, dp[i]);
  }
  for (int i = 1; i <= q; i++) {
    int c, d;
    cin >> c >> d;
    rez = 0;
    query(1, 1, m, c, d);
    if (rez >= c)
      cout << 1;
    else
      cout << 0;
  }
  return 0;
}
