#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, m, q, a[N], b[N], c[N], last[N], minr[N], f[N][20];
int main() {
  scanf("%d%d%d", &n, &m, &q);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
    c[a[i]] = i;
  }
  for (int i = 1; i <= m; ++i) {
    scanf("%d", &b[i]);
    b[i] = c[b[i]];
  }
  fill(last + 1, last + 1 + n, m + 1);
  fill(f[m + 1], f[m + 1] + 20, m + 1);
  for (int i = m; i; --i) {
    f[i][0] = last[b[i] % n + 1];
    for (int j = 1; (1 << j) <= n; ++j) {
      f[i][j] = f[f[i][j - 1]][j - 1];
    }
    last[b[i]] = i;
  }
  minr[m + 1] = m + 1;
  for (int i = m; i; --i) {
    minr[i] = i;
    for (int j = 19, t = n - 1; ~j; --j) {
      if (t >> j & 1) {
        minr[i] = f[minr[i]][j];
        t ^= 1 << j;
      }
    }
    minr[i] = min(minr[i], minr[i + 1]);
  }
  while (q--) {
    int l, r;
    scanf("%d%d", &l, &r);
    printf("%d", minr[l] <= r);
  }
  return puts(""), 0;
}
