#include <bits/stdc++.h>
using namespace std;
const int M = 2e5 + 5;
int n, m, q;
int f[M][20];
int p[M], a[M];
int pre[M], las[M], res[M];
void init() {
  pre[p[1]] = p[n];
  for (int i = 2; i <= n; i++) pre[p[i]] = p[i - 1];
  for (int i = 1; i <= m; i++) {
    f[i][0] = las[pre[a[i]]];
    for (int j = 1; j < 20; j++) f[i][j] = f[f[i][j - 1]][j - 1];
    las[a[i]] = i;
  }
  for (int i = 1; i <= m; i++) {
    int x = i, all = n - 1;
    for (int j = 19; ~j; j--)
      if (all & (1 << j)) {
        x = f[x][j];
        all -= (1 << j);
      }
    res[i] = max(res[i - 1], x);
  }
}
int solve(int l, int r) { return res[r] >= l ? 1 : 0; }
int main() {
  scanf("%d%d%d", &n, &m, &q);
  for (int i = 1; i <= n; i++) scanf("%d", p + i);
  for (int i = 1; i <= m; i++) scanf("%d", a + i);
  init();
  for (int i = 1, l, r; i <= q; i++) {
    scanf("%d%d", &l, &r);
    printf("%d", solve(l, r));
  }
  return 0;
}
