#include <bits/stdc++.h>
using namespace std;
int n, m, q, a[200010], b[200010], pos[200010], lst[200010];
int f[200010][30], G[200010][30], L[200010];
int amax(int a, int b) { return a > b ? a : b; }
int main() {
  int i, j, cnt, poss, t, l, r;
  scanf("%d%d%d", &n, &m, &q);
  for (i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    pos[a[i]] = i;
  }
  for (i = 1; i <= m; i++) {
    scanf("%d", &b[i]);
    t = a[pos[b[i]] - 1];
    if (!t) t = a[n];
    f[i][0] = lst[t];
    lst[b[i]] = i;
  }
  for (i = 1; 1 << i <= n; i++) {
    for (j = 1; j <= m; j++) {
      f[j][i] = f[f[j][i - 1]][i - 1];
    }
  }
  for (i = 1; i <= m; i++) {
    poss = i;
    cnt = n - 1;
    for (j = 20; j >= 0; j--) {
      if (cnt - (1 << j) >= 0) {
        cnt -= 1 << j;
        poss = f[poss][j];
      }
    }
    G[i][0] = poss;
  }
  for (j = 1; (1 << j) <= m; j++) {
    for (i = 1; i + (1 << j) - 1 <= m; i++) {
      G[i][j] = amax(G[i][j - 1], G[i + (1 << (j - 1))][j - 1]);
    }
  }
  L[0] = -1;
  for (i = 1; i <= m; i++) L[i] = L[i >> 1] + 1;
  for (i = 1; i <= q; i++) {
    scanf("%d%d", &l, &r);
    cnt = L[r - l + 1];
    if (amax(G[l][cnt], G[r - (1 << cnt) + 1][cnt]) >= l)
      printf("1");
    else
      printf("0");
  }
  return 0;
}
